System and method for static detection and categorization of information-flow downgraders

Patent metadata

Field	Value
Publication number	US-9275246-B2
Application number	US-57564709-A
Country	US
Kind code	B2
Filing date	Oct 8, 2009
Priority date	Oct 8, 2009
Publication date	Mar 1, 2016
Grant date	Mar 1, 2016

Abstract

A system and method for static detection and categorization of information-flow downgraders includes transforming a program stored in a memory device by statically analyzing program variables to yield a single assignment to each variable in an instruction set. The instruction set is translated to production rules with string operations. A context-free grammar is generated from the production rules to identify a finite set of strings. An information-flow downgrader function is identified by checking the finite set of strings against one or more function specifications.

First claim

What is claimed is:

1. A method for static detection and categorization of information-flow downgraders, comprising:
transforming a program stored in a memory device by statically analyzing program variables to yield a single assignment for each variable in an instruction set;
translating the instruction set to production rules with string operations to identify a finite set of strings;
generating a context-free grammar from the production rules; and
identifying an information-flow downgrader function by checking the finite set of strings against one or more function specifications, wherein the information-flow downgrader function downgrades input information by endorsing integrity and declassifying confidentiality of the information to enable high input information to flow to low program points.

2. The method as recited in claim 1 , wherein identifying includes detecting and categorizing the downgrader functions based upon a purpose the downgrader function.

3. The method as recited in claim 1 , wherein the one or more functions include a security-sensitive function in the program.

4. The method as recited in claim 1 , further comprising comparing the context free grammar with a specification of the security-sensitive function such that if the grammar satisfies the specification, the input is considered properly downgraded.

5. The method as recited in claim 4 , further comprising labeling a string to locate string-manipulating functions that modified the input and made the input specification-compliant.

6. The method as recited in claim 1 , wherein the one or more function specifications are employed to categorize the downgrader function.

7. The method as recited in claim 1 , wherein transforming the program includes transforming the program by employing pseudo notations for program variable assignments.

8. The method as recited in claim 1 , wherein the downgrader function is generated by a Web application.

9. A computer readable storage medium comprising a computer readable program for static detection and categorization of information-flow downgraders, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:
transforming a program stored in a memory device by statically analyzing program variables to yield a single assignment to each variable in an instruction set;
translating the instruction set to production rules with string operations;
generating a context-free grammar from the production rules to identify a finite set of strings; and
identifying an information-flow downgrader function by checking the finite set of strings against one or more function specifications, wherein the information-flow downgrader function downgrades input information by endorsing integrity and declassifying confidentiality of the input information to enable high input to flow to low program points.

10. The computer readable storage medium as recited in claim 9 , wherein identifying includes detecting and categorizing the downgrader functions based upon a purpose the downgrader function.

11. The computer readable storage medium as recited in claim 9 , wherein the one or more functions include a security-sensitive function in the program.

12. The computer readable storage medium as recited in claim 9 , further comprising comparing the context free grammar with a specification of the security-sensitive function such that if the grammar satisfies the specification the input is considered properly downgraded.

13. The computer readable storage medium as recited in claim 12 , further comprising labeling a string to locate string-manipulating functions that modified the input and made the input specification-compliant.

14. The computer readable storage medium as recited in claim 9 , wherein the one or more function specifications are employed to categorize the downgrader.

15. The computer readable storage medium as recited in claim 9 , wherein transforming the program includes transforming the program by employing pseudo notations for program variable assignments.

16. A method for static detection and categorization of information-flow downgraders, comprising:
transforming a program stored in a memory device by statically analyzing program variables to yield a single assignment to each variable in an instruction set;
translating the instruction set to production rules with string operations;
performing a pointer analysis on the production rules with string operations to improve precision;
generating a context-free grammar from the production rules to identify a finite set of strings;
comparing the context free grammar with a specification of a security-sensitive function such that if the grammar satisfies the specification, input information is considered properly downgraded; and
labeling a string to locate string-manipulating functions that modified an input and made the input specification-compliant to identify and categorize an information-flow downgrader function, wherein the information-flow downgrader function downgrades the input information by endorsing integrity and declassifying confidentiality of the input information to enable high information to flow to low program points.

17. The method as recited in claim 16 , wherein transforming the program includes transforming the program by employing pseudo notations for program variable assignments.

18. The method as recited in claim 17 , wherein the downgrader function is generated by a Web application.

19. A system for static detection and categorization of information-flow downgraders, comprising:
a program storage device configured to store a program, the program storage device further configured to work in conjunction with a processor to execute program instructions to detect and categorize information-flow downgraders in the program;
a static analysis framework configured to analyze an application program and to perform a static string assignment on the application program to transform program variables to yield a single assignment for each variable in an instruction set, the framework configured to translate the instruction set to production rules with string operations and generate a context-free grammar from the production rules to identify a finite set of strings; and
a comparison module configured to detect and categorize the finite set of strings by comparing the finite set of strings against one or more function specifications to identify an information-flow downgrader function, wherein the information-flow downgrader function downgrades input by endorsing integrity and declassifying confidentiality of the input to enable high information to flow to low program points.

20. The system as recited in claim 19 , wherein downgrader functions are categorized based upon a purpose of the downgrader function.

21. The system as recited in claim 19 , wherein the one or more functions include a security-sensitive function in the program.

22. The system as recited in claim 19 , wherein the comparison module compares the context free grammar with a specification of a security-sensitive function such that if the grammar satisfies the specification the input is considered properly downgraded.

23. The system as recited in claim 22 , a labeler configured to label a string to locate string-manipulating functions that modified the input and made the input specification-compliant.

24. The system as recited in claim 19 , wherein the downgrader function i

Assignees

• Haviv Yinnon
• Hay Roee
• Pistoia Marco
• Podjarny Guy
• Sharabani Adi
• Tateishi Takaaki
• Tripp Omer
• Weisman Omri
• IBM

Inventors

• Haviv Yinnon
• Hay Roee
• Pistoia Marco
• Podjarny Guy
• Sharabani Adi
• Tateishi Takaaki
• Tripp Omer
• Weisman Omri

Classifications

• G06F8/49 Primary

  Partial evaluation · CPC title

• G06F11/3608

  using formal methods, e.g. model checking, abstract interpretation (theorem proving G06N5/013) · CPC title

• G06F21/6218 Primary

  to a system of files or objects, e.g. local or distributed file system or database · CPC title

• H04L63/1416 Primary

  Event detection, e.g. attack signature detection · CPC title