Visible to the public On Computing Relevant Parameters of Decision Functions

ABSTRACT

To facilitate reasoning about modern cyber-physical systems, we wish to determine which inputs or parameters of a black-box function are relevant to the output. Adaptive software components rely on a plethora of decision-making and control functions for reconfiguration and adaptation to different contexts. Such functions can be manually written or obtained using machine learning. Here we use only oracle (black box) access to the decision function, making our approach more widely applicable, scalable, and free from the classical requirement of meticulous formal modeling. Our approach addresses two central challenges of high-assurance design: robust proofs where the correctness argument for a single context or configuration can be extended to a set of contexts or configurations, and compositional design where contexts for different configuration decisions can be automatically identified. We present two different algorithms using Hamming-distance based search and random-walk in Boolean hypercube for solving the problem of computing relevance and present theoretical results on the runtime complexity and probabilistically approximately correct (PAC) correctness guarantees. Finally, we present experimental results from compositional design of cyberphysical systems to demonstrate the value of our approach.

Dr. Susmit Jha, a Principal Computer Scientist in the Computer Science Laboratory at SRI International, is an expert in neurosymbolic approaches to Artificial Intelligence (AI) with applications to high-assurance autonomous cyberphysical systems. Dr. Jha is currently PI/co-PI on several NSF, DARPA, IARPA, and ARL projects on building creative, trustworthy, and resilient artificial intelligence methods, including DARPA Assured Autonomy, DARPA Symbiotic Design of Cyberphysical Systems, DARPA Intent-driven Design of Adaptive Systems, IARPA TrojAI, NSF Self-improving Cyberphysical Systems, NSF Duality-based Program Synthesis, and ARL Principles of Robust Learning in IoBTs CRA. Before joining SRI, Dr. Jha was a Staff Scientist at United Technologies Research Center (Raytheon), Berkeley, and a Research Scientist at Intel. At UTRC, Dr. Jha performed on several DoD projects on AI and autonomy, including DARPA Aircraft Labor In-cockpit Automation Systems, DARPA Communications under Contested Environments, and ONR Human-Machine Systems. At Intel, Dr. Jha developed approaches to AI-driven architecture design, which influenced the on-chip-interconnect design on a 14nm SoC design. Dr. Jha completed his Ph.D. from UC Berkeley in 2011. His thesis work on the automated formal synthesis of safe controllers and programs received Leon O. Chua Award for outstanding achievement in nonlinear sciences. His oracle-guided approach to program synthesis, which combines formal reasoning with machine learning from samples, received the 10-year Most Influential Paper award at IEEE/ACM International Conference on Software Engineering (ICSE), 2020. Dr. Jha has over 55 peer-reviewed publications and over 2000 citations.

Dr. Patrick Lincoln, Ph.D., is Vice President, Information and Computing Sciences and the director of the Computer Science Laboratory at SRI International. He is also the executive director of SRI's program for the Department of Homeland Security's Cyber Security Research and Development Center and director of the SRI Center for Computational Biology. Dr. Lincoln leads research in the fields of formal methods, computer security and privacy, computational biology, scalable distributed systems, and nanoelectronics. He has led multidisciplinary groups conducting high-impact research projects in symbolic systems biology, scalable anomaly detection, exquisitely sensitive biosensor systems, strategic reasoning and game theory, and privacy-preserving data sharing. He has published dozens of influential papers, holds several patents, has served on scientific advisory boards for private and publicly held companies, nonprofits, and government agencies and departments. Dr. Lincoln holds a Ph.D. in computer science from Stanford University and a B.Sc. in computer science from MIT. He has previously held positions at MCC, Los Alamos National Laboratory, and ETA Systems.

License: 
Creative Commons 2.5

Other available formats:

On Computing Relevant Parameters of Decision Functions
Switch to experimental viewer