Improving the efficiency of symbolic execution by clustering the input data based on the complexity of test generation

Authors

DOI:

https://doi.org/10.15587/1729-4061.2023.286160

Keywords:

unit testing, effective computations, dynamic code analysis, static code analysis

Abstract

The object of research is means to increase computational effectiveness for automatic unit test generation process. It provides arguments for developing new method to achieve wider use of symbolic execution in commercial software development. The main task of the research is to create adaptive code clustering method that considers test generation complexity for structural source code elements and available computational resources that will increase effectiveness of computations. It is achieved by estimating test generation complexity and balancing the it for produced clusters during clusterization. As a result, proposed clustering method is adaptive to hardware and source code variability. It is shown that developed approach provides up to 30 % increase in computation effectiveness compared to clustering based on code structural properties alone for selected samples and up to 250 % in separate cases. This is caused by balanced estimated test generation complexity within generated clusters. It limits path explosion to expected levels that match computational resources for every cluster. Estimate of test generation complexity makes it possible to stop the computation when the spent time exceeds the corresponding complexity limit. Consequently, it makes it possible to prevent performing unnecessary computations. Proposed method makes it possible to use symbolic execution in commercial software development due to higher adaptability for source code and hardware variations. It will allow to reduce expenses on early-stage software testing and provide means for determining feasibility of symbolic execution for commercial projects

Author Biographies

Roman Bazylevych, Lviv Polytechnic National University

Doctor of Technical Sciences, Professor

Department of Software

Andrii Franko, Lviv Polytechnic National University

Postgraduate Student

Department of Software

References

  1. Le, W. (2013). Segmented symbolic analysis. 2013 35th International Conference on Software Engineering (ICSE). doi: https://doi.org/10.1109/icse.2013.6606567
  2. Shen, S., Shinde, S., Ramesh, S., Roychoudhury, A., Saxena, P. (2019). Neuro-Symbolic Execution: Augmenting Symbolic Execution with Neural Constraints. Proceedings 2019 Network and Distributed System Security Symposium. doi: https://doi.org/10.14722/ndss.2019.23530
  3. Yi, Q., Yang, G. (2022). Feedback-Driven Incremental Symbolic Execution. 2022 IEEE 33rd International Symposium on Software Reliability Engineering (ISSRE). doi: https://doi.org/10.1109/issre55969.2022.00055
  4. Cadar, C., Nowack, M. (2020). KLEE symbolic execution engine in 2019. International Journal on Software Tools for Technology Transfer, 23 (6), 867–870. doi: https://doi.org/10.1007/s10009-020-00570-3
  5. Vishnyakov, A., Fedotov, A., Kuts, D., Novikov, A., Parygina, D., Kobrin, E. et al. (2020). Sydr: Cutting Edge Dynamic Symbolic Execution. 2020 Ivannikov Ispras Open Conference (ISPRAS). doi: https://doi.org/10.1109/ispras51486.2020.00014
  6. Singh, S., Khurshid, S. (2020). Parallel Chopped Symbolic Execution. Lecture Notes in Computer Science, 107–125. doi: https://doi.org/10.1007/978-3-030-63406-3_7
  7. Păsăreanu, C. S., Kersten, R., Luckow, K., Phan, Q.-S. (2019). Symbolic Execution and Recent Applications to Worst-Case Execution, Load Testing, and Security Analysis. Advances in Computers, 289–314. doi: https://doi.org/10.1016/bs.adcom.2018.10.004
  8. Bazylevych, R. P., FrankoА. V. (2022). Hierarchical model of automated test generation system. Scientific Bulletin of UNFU, 32 (4), 77–83. doi: https://doi.org/10.36930/40320412
  9. Bazylevych, R., Franko, A. (2022). Input decomposition by clusterization for symbolic execution. 2022 IEEE 17th International Conference on Computer Sciences and Information Technologies (CSIT). doi: https://doi.org/10.1109/csit56902.2022.10000433
  10. Poeplau, S., Francillon, A. (2019). Systematic comparison of symbolic execution systems. Proceedings of the 35th Annual Computer Security Applications Conference. doi: https://doi.org/10.1145/3359789.3359796
  11. Mues, M., Howar, F. (2022). GDart: An Ensemble of Tools for Dynamic Symbolic Execution on the Java Virtual Machine (Competition Contribution). Lecture Notes in Computer Science, 435–439. doi: https://doi.org/10.1007/978-3-030-99527-0_27
  12. Peitek, N., Apel, S., Parnin, C., Brechmann, A., Siegmund, J. (2021). Program Comprehension and Code Complexity Metrics: A Replication Package of an fMRI Study. 2021 IEEE/ACM 43rd International Conference on Software Engineering: Companion Proceedings (ICSE-Companion). doi: https://doi.org/10.1109/icse-companion52605.2021.00071
  13. Bazylevych, R., Palasinski, M., Bazylevych, L., Yanush, D. (2013). Partitioning optimization by iterative reassignment of the hierarchically built clusters with border elements. 2013 2nd Mediterranean Conference on Embedded Computing (MECO). doi: https://doi.org/10.1109/meco.2013.6601362
Improving the efficiency of symbolic execution by clustering the input data based on the complexity of test generation

Downloads

Published

2023-08-31

How to Cite

Bazylevych, R., & Franko, A. (2023). Improving the efficiency of symbolic execution by clustering the input data based on the complexity of test generation . Eastern-European Journal of Enterprise Technologies, 4(2 (124), 17–25. https://doi.org/10.15587/1729-4061.2023.286160

Issue

Vol. 4 No. 2 (124) (2023): Information technology. Industry control systems

Section

Information technology

License

Copyright (c) 2023 Roman Bazylevych, Andrii Franko

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.