4/26/10'1'Reexamining Black Box and White Box Sampling Strategies for Testing Large-Scale Configurable Systems Adam Porter Configuration Spaces Grow Fast • Exhaustive testing is generally too expensive – Cfg spaces large, individual tests are expensive • Nearest Neighbor Search (MySQL) – 110k cfgs, 3hrs/cfg, 50 cpus took > 6 mos • Component-Based System Testing (Intercom) – Very restricted subset had ~ 3500 cfgs, ~ 3hrs/cfg, takes ~15 mos.4/26/10'2'Possible Values Product Line Options (factors) Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None Example: Phone S/W Product Line Possible Values Product Line Options (factors) Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None Example: Phone S/W Product Line4/26/10'3'Possible Values Product Line Options (factors) Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None Example: Phone S/W Product Line 6 Possible Values Product Line Options (factors) Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None Example: Phone S/W Product Line4/26/10'4'7 Possible Values Product Line Options (factors) Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None Example: Phone S/W Product Line 8 Possible Values Product Line Options (factors) Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None Example: Phone S/W Product Line4/26/10'5'9 Possible Values Product Line Options (factors) Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None Example: Phone S/W Product Line A Combinatorial Problem Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None4/26/10'6'A Combinatorial Problem Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None 3 A Combinatorial Problem Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None 3 x 34/26/10'7'A Combinatorial Problem Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None 3 x 3 x 3 A Combinatorial Problem Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None 3 x 3 x 3 x 2 x 24/26/10'8'• This example has 33x22=108 cfgs • A subset of MySQL we tested in previous work had ~72,000,000 cfgs – At 3hrs per test, would take ~24,650 cpu years to test A Combinatorial Problem Display Email Viewer Camera Video Camera Video Ringtones 16 Million Colors Graphical 2 Megapixels Yes Yes 8 Million Colors Text 1 Megapixel No No Black and White None None Combinatorial Interaction Testing (CIT) • Can’t test entire cfg space • CIT systematically samples cfg space • Covering arrays – Select a subset of cfgs such that all t-way combs of values occur at least once – t is called the testing strength4/26/10'9'Display Email Viewer Camera Video V. Ringtones 1 16 Million Colors None 1 Megapixel Yes Yes 2 8 Million Colors Text None No No 3 16 Million Colors Text 2 Megapixels No Yes 4 Black and White None None No Yes 5 8 Million Colors None 2 Megapixels Yes No 6 16 Million Colors Graphical None Yes No 7 Black and White Text 1 Megapixel Yes No 8 8 Million Colors Graphical 1 Megapixel No Yes 9 Black and White Graphical 2 Megapixels Yes Yes A 2-way Covering Array Display Email Viewer Camera Video V. Ringtones 1 16 Million Colors None 1 Megapixel Yes Yes 2 8 Million Colors Text None No No 3 16 Million Colors Text 2 Megapixels No Yes 4 Black and White None None No Yes 5 8 Million Colors None 2 Megapixels Yes No 6 16 Million Colors Graphical None Yes No 7 Black and White Text 1 Megapixel Yes No 8 8 Million Colors Graphical 1 Megapixel No Yes 9 Black and White Graphical 2 Megapixels Yes Yes Sampling the Space4/26/10'10'Display Email Viewer Camera Video V. Ringtones 1 16 Million Colors None 1 Megapixel Yes Yes 2 8 Million Colors Text None No No 3 16 Million Colors Text 2 Megapixels No Yes 4 Black and White None None No Yes 5 8 Million Colors None 2 Megapixels Yes No 6 16 Million Colors Graphical None Yes No 7 Black and White Text 1 Megapixel Yes No 8 8 Million Colors Graphical 1 Megapixel No Yes 9 Black and White Graphical 2 Megapixels Yes Yes Sampling For Testing Display Email Viewer Camera Video V. Ringtones 1 16 Million Colors None 1 Megapixel Yes Yes 2 8 Million Colors Text None No No 3 16 Million Colors Text 2 Megapixels No Yes 4 Black and White None None No Yes 5 8 Million Colors None 2 Megapixels Yes No 6 16 Million Colors Graphical None Yes No 7 Black and White Text 1 Megapixel Yes No 8 8 Million Colors Graphical 1 Megapixel No Yes 9 Black and White Graphical 2 Megapixels Yes Yes Sampling For Testing4/26/10'11'CIT Summary • CIT approaches used to limit test suite size – e.g. covering arrays • Effort concentrated on these configurations – May still be too many in practice – MySQL case study – ~1k cfgs/release ,