Комбинаторная генерация программных конфигураций ОС
https://doi.org/10.15514/ISPRAS-2012-23-20
Аннотация
В статье представлен метод генерации тестов для конфигурационного тестирования на основе покрывающих наборов, т.е., обеспечивающая покрытие всех возможных комбинаций пар, троек и т.д., значений параметров конфигурации. Новым элементом в предлагаемом методе является учет условий использования отдельных параметров, который вносит коррективы как в учет покрываемых комбинаций, так и в построение отдельных тестов. Данный метод использован на практике для генерации тестовых программных конфигураций операционной системы реального времени, приведены результаты этого применения.
Список литературы
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. Кулямин В. В., Петухов А. А. Обзор методов построения покрывающих наборов. Программрование, 37(3):3-41, 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.
Рецензия
Для цитирования:
Кулямин В.В. Комбинаторная генерация программных конфигураций ОС. Труды Института системного программирования РАН. 2012;23. https://doi.org/10.15514/ISPRAS-2012-23-20
For citation:
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
Послать статью по эл. почте 