Note: This is an historic document. We are no longer maintaining the
content, but it may have value for research purposes. Pages linked to
from the document may no longer be available.
Function Extraction Technology:
Prinicpal Investigator: Richard C. Linger
Automated Calculation of Computer Progam Behavior
Function extraction (FX) is a disruptive new technology with potential to improve the economics of software development and increase the dependability of software systems.
Function Extraction Concepts
Present-day, labor-intensive methods of software engineering are increasingly overwhelmed by the scope and complexity of modern systems. We believe software engineering must be transformed into a more computational discipline based on science foundations that enable fast and dependable software development. Other engineering disciplines have made this transformation to rigorous computational analysis of subject matter to their everlasting benefit.
In particular, it is vital that software engineers understand all of the behavior of software, because unknown behavior can harbor incorrect functionality and security vulnerabilities. What is needed is a precise and comprehensive "all cases of behavior" view of what software does, something that is unavailable with current software engineering technology.
The SEI's CERT Program is developing the emerging technology of function extraction, which applies mathematical foundations to automate calculation of the behavior of software to the maximum extent possible. The objective is to replace slow and fallible manual methods of code reading and inspection with fast and correct computation of behavior.
Computing the behavior of software requires deriving its net functional effect, that is, how it transforms inputs into outputs in all circumstances of use. That information can be presented to analysts in non-procedural behavior databases that define all the possible effects a program can have, essentially, the "all cases of behavior" view. The result is to move from an uncertain understanding of software derived in human time scale (days) to a precise understanding computed in machine time scale (seconds).
Controlled experimentation shows FX automation is substantially faster than manual methods for determining software functionality, and that programmers are many times more productive in analyzing software with FX. An FX system that computes behavior for programs written in, or compiled into, Intel assembly language is currently under development. This system is initially targeting malware analysis, to help provide analysts with fast understanding of intruder intentions and strategies.
Function Extraction Application
FX technology can be applied to any language, and promises to be particularly valuable in meeting dependability requirements for DoD systems. Function extraction will impact many aspects of the software engineering lifecycle, including:
- Development: A few lines of code can be written and submitted to a function extractor to determine if they indeed do what is required.
- Verification: Programs can be submitted to a function extractor to derive their "as-built" specifications for verification against requirements.
- Security: Security properties of software can be expressed in functional form and checked against the behavior databases produced by function extractors.
- Testing: Because function extraction computes software behavior, testing for functional correctness provide little additional information, and can be reduced.
- Legacy systems: Function extraction can be applied to legacy systems to recover specification and design information to enable informed modification and evolution.
- Malware detection: Malicious code embedded within software has functional effects that are revealed in the behavior databases produced by function extractors.
- Malware analysis: The functional intentions of malicious code can be quickly revealed by function extractors in order to develop countermeasures.
- Assurance: Potential problems with tampering, unknown sourcing, or malicious content in software can be revealed through behavior computation.
Linger, Richard, Daly, Tim, Pleszkoch, Mark. Function Extraction (FX) Research for Computation of Software Behavior: 2010 Development and Application of Semantic Reduction Theorems for Behavior Analysis (CMU/SEI-2011-TR-009). Software Engineering Institute, Carnegie Mellon University, 2011
Linger, Richard, C.,Pleszkoch, Mark G., Burns, Luanne, Hevner, Alan R., Walton, Gwendolyn,H.
Next Generation Software Engineering:Function Extraction for Computation
of Software Behavior, Proceedings of Hawaii International Conference on System Sciences (HICSS-40)
Bartholomew, Redge, Burns, Luanne, Daly, Timothy, Linger, Rick, Prowell,
Stacy, Function Extraction,
Computation for Aerospace Software Verification and Certification, AIAA Conference on Information Technology, American Institute of Aeronautics and Astronautics, Monterey, CA, 2007
Pleszkoch, Mark G., Linger, Richard, C., Hevner, Alan R,
Function Extraction into Sofware Testing, The Data Base for Advances in Information Systems: Special Issue on Software Systems Testing, ACM SIGMIS, New York, NY, 2008
Walton, Gwendolyn, Longstaff, Thomas, Linger, Richard, C.,
Computational Evaluation of Software Security
Attributes, Proceedings of Hawaii International Conference on System Sciences (HICSS-42), IEEE Computer Society Press, Los Alimitos, CA, 2009
Burns, Luanne, Daly, Timothy, FXplorer:
Exploration of Computed Software Behavior: A New Approach to Understanding and
Verification, Proceedings of Hawaii International Conference on System Sciences (HICSS-42)
Last updated February 28, 2011