A Data-Driven Finite State Machine Model for Analyzing Security Vulnerabilities

This paper combines an analysis of data on security vulnerabilities (published in Bugtraq database) and a focused source-code examination to develop a finite state machine (FSM) model to depict and reason about security vulnerabilities. An in-depth analysis of the vulnerability reports and the corresponding source code of the applications leads to three observations: (i) exploits must pass through multiple elementary activities, (ii) multiple vulnerable operations on several objects are involved in exploiting a vulnerability, and (iii) the vulnerability data and corresponding code inspections allow us to derive a predicate for each elementary activity.  Each predicate is represented as a primitive FSM (pFSM). Multiple pFSMs are then combined to create an FSM model of vulnerable operations and possible exploits. The proposed FSM methodology is exemplified by analyzing several types of vulnerabilities reported in the data: stack buffer overflow, integer overflow, heap overflow, input validation vulnerabilities, and format string vulnerabilities. For the studied vulnerabilities, we identify three types of pFSMs, which can be used to analyze operations involved in exploiting vulnerabilities and to identify the security checks to be performed at the elementary activity level. A demonstration of the practical usefulness of the FSM modeling approach was the discovery of a new heap overflow vulnerability now published in Bugtraq.