Abstract
Legion is a grey-box coverage-based concolic tool that aims to balance the complementary nature of fuzzing and symbolic execution to achieve the best of both worlds. It proposes a variation of Monte Carlo tree search (MCTS) that formulates program exploration as sequential decision-making under uncertainty guided by the best-first search strategy. It relies on approximate path-preserving fuzzing, a novel instance of constrained random testing, which quickly generates many diverse inputs that likely target program parts of interest. In Test-Comp 2020 [1], the prototype performed within 90% of the best score in 9 of 22 categories.
This research was supported by Data61 under the Defence Science and Technology Group’s Next Generation Technologies Program.
G. Ernst—Jury Member.
Chapter PDF
Similar content being viewed by others
References
Beyer, D.: Second competition on software testing: Test-comp 2020. In: Proc. of Fundamental Aspects of Software Engineering (FASE). LNCS, Springer (2020), https://www.sosy-lab.org/research/pub/2020-FASE.Second_Competition_on_Software_Testing_Test-Comp_2020.pdf
Bjørner, N., Phan, A.D., Fleckenstein, L.: \(\nu \)Z-an optimizing SMT solver. In: Proc. of Tools and Algorithms for the Construction and Analysis of Systems (TACAS). LNCS, vol. 9035, pp. 194–199. Springer (2015). https://doi.org/10.1007/978-3-662-46681-0_14
Browne, C.B., Powley, E., Whitehouse, D., Lucas, S.M., Cowling, P.I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., Colton, S.: A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games 4(1), 1–43 (2012). https://doi.org/10.1109/TCIAIG.2012.2186810
Dutra, R., Laeufer, K., Bachrach, J., Sen, K.: Efficient sampling of SAT solutions for testing. In: Proc. of the International Conference on Software Engineering (ICSE). pp. 549–559. ACM (2018). https://doi.org/10.1145/3180155.3180248
Godefroid, P., Levin, M.Y., Molnar, D.A., et al.: Automated whitebox fuzz testing. In: Proc. of Network and Distributed Systems Security (NDSS). vol. 8, pp. 151–166. The Internet Society (2008)
King, J.C.: Symbolic execution and program testing. Communications of the ACM 19(7), 385–394 (1976). https://doi.org/10.1145/360248.360252
Takanen, A., Demott, J.D., Miller, C., Kettunen, A.: Fuzzing for software security testing and quality assurance. Artech House (2018)
Wang, F., Shoshitaishvili, Y.: Angr - the next generation of binary analysis. In: Proc. of Cybersecurity Development (SecDev). pp. 8–9. IEEE (2017). https://doi.org/10.1109/SecDev.2017.14
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2020 The Author(s)
About this paper
Cite this paper
Liu, D., Ernst, G., Murray, T., Rubinstein, B.I.P. (2020). Legion: Best-First Concolic Testing (Competition Contribution). In: Wehrheim, H., Cabot, J. (eds) Fundamental Approaches to Software Engineering. FASE 2020. Lecture Notes in Computer Science(), vol 12076. Springer, Cham. https://doi.org/10.1007/978-3-030-45234-6_31
Download citation
DOI: https://doi.org/10.1007/978-3-030-45234-6_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-45233-9
Online ISBN: 978-3-030-45234-6
eBook Packages: Computer ScienceComputer Science (R0)