Combinatorial generation of operation system software configurations
https://doi.org/10.15514/ISPRAS-2012-23-20
Abstract
tion 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.
References
1. Cohen D. M., Dalal S. R., Parelius J., Patton G. C. The Combinatorial Design Approach to Automatic Test Generation. IEEE Software, 13(5):83-87, 1996.
2. Kuliamin V., Petukhov A. A survey of methods for constructing covering arrays. Programming and Computer Software 37(3): 121-146, 2011.
3. Greene C. Sperner families and partitions of a partially ordered set. In Combinatorics, Hall M. Jr. van Lint J., eds. Dordrecht, Holland, 1975, pp. 277-290.
4. Hartman A. Software and Hardware Testing Using Combinatorial Covering Suites. Proc. of Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications, 2005, pp. 266-327.
5. Bryce R. C., Colbourn C. J., Cohen M. B. A Framework of Greedy Methods for Constructing Interaction Test Suites. Proc. of Intl. Conf. on Software Engineering (ICSE’05), 2005, pp. 146-155.
6. Cook S. The complexity of theorem proving procedures. Proc of 3-rd Annual ACM Symposium on Theory of Computing, 1971. pp. 151-158.
7. Davis M., Logemann G., Loveland D. A machine program for theorem-proving. Communications of the ACM 5(7):394-397, 1962.
8. Schoning T. A probabilistic algorithm for k-SAT and constraint satisfaction problems. Proc. of 40-th Annual Symposium on Foundations of Computer Science, 1999, pp. 410-414.
9. Paturi R., Pudlak P., Saks M. E., Zani F. An improved exponential-time algorithm for k-SAT. Journal of the ACM, 52(3):337-364, 2005.
10. Krom M. R. The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 13(1-2):15-20, 1967.
11. Even S., Itai A., Shamir A. On the complexity of time table and multi-commodity flow problems. SIAM Journal on Computing, 5(4):691-703, 1976.
12. Aspvall B., Plass M. F., Tarjan R. E. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, 8(3):121-123, 1979.
Review
For citations:
Kuliamin V.V. Combinatorial generation of operation system software configurations. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2012;23. (In Russ.) https://doi.org/10.15514/ISPRAS-2012-23-20
Email this article 