← DARPA STAC
Sections 8–11

Publications and Presentations

RULER: A System to Detect Resource Usage Vulnerabilities Within Software

Contents

8. Publications and Presentations

8.1 Journal Papers

  1. Ahmed Tamrawi and Suresh Kothari, “Projected Control Graph for Computing Relevant Program Behaviors”, Science of Computer Programming Volume 163, Pages 93-114, October 2018.

8.2 Book Chapter

  1. Suresh Kothari, Ganesh Ram Santhanam, Payas Awadhutkar, Benjamin Holland, Jon Mathews, and Ahmed Tamrawi, “Catastrophic Cyber Physical Malware,” Springer Verlag Publishers, October 2018, Pages 1-41.

8.3 Peer-Reviewed Conference Papers

  1. Payas Awadhutkar, Ganesh Ram Santhanam, Benjamin Holland, Suresh Kothari, “DISCOVER: Detecting Algorithmic Complexity Vulnerabilities,” 27th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE).
  2. Derrick Lockwood, Benjamin Holland, Suresh Kothari, “MOCKINGBIRD: A Framework for Enabling Targeted Dynamic Analysis of Java Programs,” 41st International Conference on Software Engineering (ICSE 2018), Montreal, May 2019.
  3. Ahmed Tamrawi, Sharwan Ram, Payas Awadhutkar, Benjamin Holland, Ganesh Ram Santhanam, Suresh Kothari, “DySDoc3 – DynaDoc: Automated On-Demand Context-Specific Documentation,” 2018 DOCGEN Challenge Workshop at the IEEE International Conference on Software Maintenance Evolution (ICSME 2018), Madrid, Spain, September 25, 2018, (Best Tool Award).
  4. Suresh Kothari, “Demystifying Cyber-Physical Malware,” 40th International Conference on Software Engineering (ICSE 2018), Technical Briefing, Sweden, Gothenburg, May 27-June 3 2018.
  5. Benjamin Holland, Payas Awadhutkar, Suresh Kothari, Ahmed Tamrawi, Jon Mathews, “COMB: Computing Relevant Program Behaviors,” 40th International Conference on Software Engineering (ICSE 2018), Sweden, Gothenburg, May 27-June 3 2018.
  6. Ganesh Ram Santhanam, Ben Holland, Suresh Kothari, Nikhil Ranade, “Human-on-the-loop-automation for Detecting Software Side Channel Vulnerabilities,” 13th International Information Systems Security Conference (ICISS 2017), Bombay I.I.T., Springer LNCS 10717, pp. 209-230, December 2017.
  7. Payas Awadhutkar, Ganesh Ram Santhanam, Ben Holland, Suresh Kothari, “Intelligence Amplifying Loop Complexity Characterizations for Detecting Algorithmic Complexity Vulnerabilities,” the 24th Asia-Pacific Software Engineering Conference (APSEC), December 2017.
  8. Suresh Kothari, Payas Awadhutkar, Ahmed Tamrawi, Jon Mathews, “Modeling Lessons from Verifying Large Software Systems for Safety and Security,” Proceedings of the 2017 Winter Simulation Conference, November 2017.
  9. Ganesh Ram Santhanam*, Ben Holland, Jon Mathews, Suresh Kothari, “Interactive Visualization Toolbox to Detect Sophisticated Android Malware,” the 14th IEEE Symposium on Visualization for Cyber Security (VizSec), October 2017.
  10. Ben Holland, Ganesh Ram Santhanam, Suresh Kothari, “Transferring state-of-the-art immutability analyses: An experimentation toolbox and accuracy benchmark,” IEEE International Conference on Software Testing, Verification and Validation, Tokyo, Japan, March 2017.
  11. Ahmed Tamrawi, Suresh Kothari, “APSEC 2016 – Projected Control Graph for Accurate and Efficient Analysis of Safety and Security Vulnerabilities,” 23rd Asia-Pacific Software Engineering Conference, Hamilton, New Zealand, December 6-9, 2016. (Invited for journal publication)
  12. Benjamin Holland+, Ganesh Santhanam*, Payas Awadhutkar+, Suresh Kothari, “Statically-informed Dynamic Analysis Tools to Detect Algorithmic Complexity Vulnerabilities,” IEEE Source Code Analysis and Manipulation (SCAM) Conference, Raleigh, North Carolina, October 1-3, 2016.
  13. Ahmed Tamrawi, Payas Awadhutkar, Suresh Kothari, “Insights for Practicing Engineers from a Formal Verification Study of the Linux Kernel,” Formal Verification for Practicing Engineers Workshop, IEEE ISSRE 2016, Ottawa, Canada, October 23-27, 2016 (Invited for journal publication).
  14. Suresh Kothari, Ahmed Tamrawi, and Jon Mathews, “Human-Machine Resolution of Invisible Control Flow,” IEEE International Conference on Program Comprehension (ICPC 2016), pp. 226-229, May 15-16, Austin, Texas, May 15-16, 2016.
  15. Suresh Kothari, Ahmed Tamrawi, and Jon Mathews, “Refactoring Verification: Accuracy, Efficiency and Scalability through Human-Machine Collaboration,” A Technical Briefing Paper, IEEE International Conference on Software Engineering (ICSE 2016), Austin, Texas, May 15-19, 2016.
  16. Suresh Kothari, Ahmed Tamrawi, Jeremías Sauceda, and Jon Mathews, “Let’s Verify Linux: Accelerated Learning of Analytical Reasoning through Automation and Collaboration,” a Software Engineering Education Track (SEET) paper, IEEE International Conference on Software Engineering (ICSE 2016), Austin, Texas, May 15-19, 2016.
  17. Suresh Kothari, “Software Engineering Research Lab to Airplanes, Orion and Beyond,” a Software Engineering Research and Industry Practice (SER&IP) Workshop paper, IEEE International Conference on Software Engineering (ICSE 2016), Austin, Texas, May 15-19, 2016 (Best Paper Award).

8.4 Keynotes and Invited Talks given by Suresh Kothari

  1. “An 18th-century Mathematician, a $336 Million Patent, and Software Verifiability,” CyLab Distinguished Seminar Series at Carnegie Mellon University, April 2019.
  2. “An 18th-century Mathematician, a $336 Million Patent, and Software. Experimentation,” International Conference on Security and Privacy, Jaipur, India, January 11, 2019 (Keynote Talk).
  3. “An 18th-century Mathematician, a $336 Million Patent, and Software Experimentation,” Computer Science Department, University of British Columbia, October 2019.
  4. “Software Security Headaches: Analgesic or Hospital,” Security of Information and Networks (SIN 2017), Manipal University, Jaipur, India, October 14, 2017 (Keynote talk).
  5. “Reflections on Applying Mathematics to Solve Hard Software Problems,” University of Central Florida, August 29, 2017.
  6. “Demystifying Cybersecurity for CPS Community,” MathWorks Research Summit, Boston, June 4, 2017.
  7. “Euler, the 336 Million Dollar Software Patent: Reflecting on How to Solve Hard Software Problems,” ACSS2017, Patna, India, March 19, 2017.
  8. “Euler, the 336 Million Dollar Software Patent: Reflecting on How to Solve Hard Software Problems,” University of Auckland, Auckland, New Zealand, December 2, 2016.
  9. “Euler, the 336 Million Dollar Software Patent: Reflecting on How to Solve Hard Software Problems,” Auckland University of Technology, Auckland, New Zealand, December 1, 2016.
  10. “Euler, the 336 Million Dollar Software Patent: Reflecting on How to Solve Hard Software Problems,” Fraunhofer Institute, Baltimore, November 3, 2016.
  11. Insights for Practicing Engineers from a Formal Verification Study of the Linux Kernel,” Plenary Talk, Formal Verification for Practicing Engineers Workshop at ISSRE 2016, October 5, 2016 (Plenary Talk).
  12. Technical Briefing, International Conference on Software Engineering, Austin, May 17, 2016.
  13. “Rethinking Verification: Accuracy, Efficiency, and Scalability through Human-Machine Collaboration,” Georgia Institute of Technology, Atlanta, May 12, 2016.
  14. “Rethinking Malware Detection: Accuracy, Efficiency, and Scalability through Human-Machine Collaboration,” University of Maryland, Baltimore, February 17, 2016.
  15. “Program Analysis and Reasoning for Hard-to-Detect Software Vulnerabilities,” Jadavpur University, Kolkata, India, December 17, 2015.
  16. “Modeling Critical Software Systems for Cybersecurity and Safety,” Tata Research Design and Development Center (TRDDC), Pune, India, December 7, 2015.
  17. “Evidence-Enabled Collaborative Verification for Cybersecurity and Safety of Critical Software Systems,” Government of India Center for Development of Advanced Computing (CDAC), Pune, November 24, 2015.
  18. “Visual Models to Solve Hard Problems at the Intersection of Cybersecurity and Software Reliability,” Rockwell Collins Headquarters, Cedar Rapids, Iowa, October 22, 2015.

8.5 Tutorials and Short Courses

  1. Suresh Kothari, “Software Engineering and Cybersecurity,” short course at Indian Institute of Technology, Jammu, India, January 7-9, 2019.
  2. Suresh Kothari and Ben Holland, “Systematic Exploration of Critical Software for Catastrophic Cyber-Physical Malware,” MILCOM Tutorial, Baltimore, October 29, 2018.
  3. Suresh Kothari, “How Mathematics can save us from catastrophic cyber attacks,” ICISS Tutorial, Bombay I.I.T., India, December 17, 2017.
  4. Suresh Kothari, Ben Holland, “Learn to analyze and verify large software for cybersecurity and safety,” MILCOM Tutorial, Baltimore, October 25, 2017.
  5. Suresh Kothari, GIAN 2017 – Analytical Reasoning and Experiential Learning with Applications to Software Analysis, MNIT, Jaipur, India, October 9-15, 2017.
  6. Suresh Kothari, Workshop on Learn to Understand, Analyze, and Verify Large Software, National Institute of Technology, Patna, India, March 20-22, 2017.
  7. Suresh Kothari, Ben Holland, Discovering Information Leakage Using Visual Program Models, MILCOM 2016, Baltimore, November 2, 2016.
  8. Suresh Kothari, Jeremías Sauceda, Mission-Critical Software Assurance Engineering Beyond Testing, Bug Finders, Metrics, Reliability Analysis, and Formal Verification, ISSRE 2016, Ottawa, Canada, October 25, 2016.
  9. Suresh Kothari, Ben Holland, GIAN 2016 – Managing Complexity, Security, and Safety of Large Software, MNIT, Jaipur, India, September 12-16, 2016. (Sponsored by the Government of India).
  10. Suresh Kothari, Ben Holland, Learn to Build Automated Software Analysis Tools with Graph Paradigm and Interactive Visual Framework, ASE 2016, Singapore, September 4, 2016.
  11. Suresh Kothari, Ben Holland, Practical program analysis for discovering Android malware, The Premier International Conference for Military Communications (MILCOM 2015), Tampa, Florida, October 28, 2015. http://www.afcea.org/events/milcom/Tutorials/tutorials.pdf
  12. Suresh Kothari, Ben Holland, Hard problems at the intersection of cybersecurity and software reliability, International Symposium on Software Reliability Engineering (ISSRE 2015), NIST, Gaithersburg, Maryland, November 3, 2015.
  13. Suresh Kothari, Ben Holland, Computer-aided collaborative validation of large software, IEEE Automated Software Engineering Conference (ASE 2015), Lincoln, Nebraska, November 3, 2015. http://ase2015.unl.edu/#computer-aided-collaborative-validation-tutorial
  14. Suresh Kothari, Program Analysis and Reasoning for Hard to Detect Software Vulnerabilities, International Conference on Information Systems Security (ICISS 2015), Kolkata, India, December 17, 2015. http://www.iciss.org.in/iciss/tutorialsp.html

9. References

  1. Turing, Alan, “On computable numbers, with an application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, Vol. 2, no. 42, pp. 230-265, 1936.
  2. “Continuum hypothesis”, http://en.wikipedia.org/wiki/Continuum_hypothesis. Accessed October 18, 2019.
  3. “Gödel's incompleteness theorems”, https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems Accessed October 18, 2019.
  4. “Paul Cohen (mathematician),” http://en.wikipedia.org/wiki/Paul_Cohen_(mathematician). Accessed October 18, 2019.
  5. Wei, Tao, Jian Mao, Wei Zou, and Yu Chen. "A new algorithm for identifying loops in decompilation." In International Static Analysis Symposium, pp. 170-183. Springer, Berlin, Heidelberg, 2007.
  6. Ahmed Tamrawi and Suresh Kothari, “Projected Control Graph for Computing Relevant Program Behaviors”, Science of Computer Programming Vol. 163, Pages 93-114, October 2018.

10. Appendix

10.1 Atlas Platform

RULER is implemented as a set of Eclipse plug-ins, which use Atlas as the reference implementation of XCSG.

Atlas uses Soot to produce the Jimple intermediate representation of Java bytecode. Jimple is a typed, three-address code, simplified representation of bytecode containing only 15 different instructions. More information about Soot and Jimple can be found at the Soot Sable homepage.

Atlas analyzes Jimple to import it into an eXtensible Common Software Graph (XCSG) compliant program graph. The following discussion is a very brief overview intended to help users get started, and focuses on XCSG as it pertains to Jimple.

In a nutshell, XCSG represents information from the AST, and conservative approximations of control flow and data flow. Most nodes are organized according to lexical nesting using Contains edges, the subgraph of which forms a tree. When visualized, Contains edges are displayed as nodes nested within nodes.

A typical path along Contains edges down to a Method goes through nodes with the following XCSG tags: Project -> Package -> Type -> Method. Fields are siblings of Methods, under the Type.

Possible invocations are represented between Methods by Call edges.

ControlFlow_Nodes and DataFlow_Nodes are embedded under Methods. All DataFlow_Nodes are immediately under a ControlFlow_Node (by a Contains edge). In XCSG for Jimple, ControlFlow_Nodes may appear under a TrapRegion.

ControlFlow_Nodes are connected via ControlFlow_Edges. DataFlow_Nodes are likewise connected by DataFlow_Edges. Operators are sub-kinds of DataFlow_Nodes. As translated by Atlas, each Field is represented by a single node, which results in an object-insensitive approximation. Other approximations may be added by RULER.

For additional help interpreting Smart Views, open the “Element Detail View” (Use Window -> Show View -> Other… ). The Element Detail View displays the tags and attributes of any nodes and edges, which have been selected, whether they are in the text editor or in a graph. Buttons in the Element Detail View toolbar can be used to view a graph of the XCSG tag hierarchy relevant to the current selection.

More information about XCSG can be found on the XCSG wiki pages.

More information about Atlas APIs can be found on the Atlas wiki.

The 2026 republication of the report has made minor changes to match ENSOFT’s current branding and other minor updates that do not affect the substance.

11. List of Symbols, Abbreviations, and Acronyms

  • AC - Algorithmic Complexity
  • API - Application Programming Interface
  • CFG - Control Flow Graph
  • CFR - Class File Reader
  • ExCFG - Control Flow Graph with Exceptional Control Flows
  • IO - Input and Output
  • IPCG - Interprocedural Projected Control Graph
  • JDK - Java Development Kit
  • LCG - Loop Call Graph
  • LTC - Loop Termination Conditions
  • LTD - Loop Termination Dependency Graph
  • PCG - Projected Control Graph
  • RULER - Resource Usage vuLnerability identifiER
  • SC - Side Channel
  • STRU - Space/Time Resource Usage
  • TDA - Targeted Dynamic Analysis
  • TDG - Termination Dependence Graph
  • XCSG - eXtensible Common Software Graph