Topseed: Learning Seed Selection Strategies for Symbolic Execution from Scratch

What is it about?

This paper introduces TopSeed, a new approach to make symbolic execution more effective. Symbolic execution is a software testing technique that explores different program paths to find program vulnerability or increase code coverage. Since most state-of-the-art techniques have overlooked the functionality "seeding", which initializes program entry states for exploration. TopSeed focuses on the overlooked step of seed selection from candidate seed inputs generated during testing. Instead of relying on a predefined seed corpus, TopSeed learns to automatically select promising seeds by utilizing a customized online learning algorithm during interaction.

Featured Image

Photo by Markus Spiske on Unsplash

Photo by Markus Spiske on Unsplash

Why is it important?

Symbolic execution is powerful but limited by two long-standing challenges: state explosion (too many possible execution paths) and expensive constraint solving (heavy use of SMT solvers). Good seeds reduce these costs by shifting the program entry states to the stronger starting points. Experiments show that integrating TopSeed with existing state-of-the-art techniques improves branch coverage by over 30% on average and discovers more bugs than using those techniques alone or with random seeds. This makes symbolic execution more scalable and reliable for testing large real-world programs.

Perspectives