« Quick authentication using mobile devices and QR Codes | Main | Galois awarded AFRL/OSD project in hardware security »
Tuesday
Jan042011

Tech Talk: Control-flow Graph Guided Exploration in DDT

Galois is pleased to host the following tech talk. These talks are open to the interested public. Please join us!

 

title: Control-flow Graph Guided Exploration in DDT

 

presenter: Rebekah Leslie

 

time: Tuesday, 11 January 2011, 10:30am

 

location:
Galois Inc.
421 SW 6th Ave. Suite 300, Portland, OR, USA
3rd floor of the Commonwealth building)

 

abstract: The existing implementation of DDT uses a depth-first search algorithm to drive the exploration of new paths for testing. This algorithm provides full coverage of the program under test, but is limited by the fact that the number of paths increases exponentially with the size of the program. By employing the control-flow graph information of the program under test, we can direct the testing process towards program paths that contain unvisited points and therefore obtain full branch coverage in a smaller number of tests than would be required by the original depth-first search algorithm. We will present two uses of control-flow graph information in DDT. The first use is a refinement of depth-first search where control-flow graph information is used to prune the search space to eliminate unnecessary tests. The second use is in the context of a prioritized work-queue that forms the basis for a variety of sophisticated search algorithms that exploit different heuristics.

 

bio: Rebekah Leslie is a PhD student at Portland State University working with Mark Jones on the Hasp project. Her primary research focus is the connection between operating systems and functional programming languages. Rebekah Leslie has also worked on information-flow security, which was a major focus of her early PhD studies. Prior to moving to Oregon, Rebekah received a BS in Computer Engineering from the University of Oklahoma where she worked with Rex Page.

Reader Comments

There are no comments for this journal entry. To create a new comment, use the form below.

PostPost a New Comment

Enter your information below to add a new comment.

My response is on my own website »
Author Email (optional):
Author URL (optional):
Post:
 
Some HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>