Proceedings of ISP RAS

Combinatorial generation of operation system software configurations.

V.V. Kuliamin.


The paper presents an operating system configuration test generation method based on construction of covering arrays, that is ensuring coverage of all pairs, triple, etc. of configuration parameters values. The method combines known optimal algorithm for binary pairwise coverage array generation with further greedy construction of non-binary part of the array. Novelty of the method proposed is taking into account parameters usage conditions, that is constraints on parameters values, which should be obeyed to force the operating system under test to use the value of certain parameter. Usage conditions require to change both accounting of tuples covered and test construction process, which includes now the parametres assignments making all the necessary constraints to hold. Construction of such an assignment uses satisfiability check based on well-known Aspvall-Plass-Tarjan algorithm. The method proposed is applied in configuration test generation for real-time operating system with several hundreds configuration parameters, the results of this application demonstrate effectiveness of the method — usually several seconds is enough for generation of up to thousand different configurations (taking in account only analysis and generation, without input and output phases) where dozens of usage conditions are satisfied.


configuration testing; covering array; test generation


Proceedings of the Institute for System Programming, vol. 23, 2012, pp. 359-370.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2012-23-20

Full text of the paper in pdf (in Russian) Back to the contents of the volume