Responsibility Analysis by Abstract Interpretation

Chaoqiang Deng, Patrick Cousot

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given a behavior of interest in the program, statically determining the corresponding responsible entity is a task of critical importance, especially in program security. Classical static analysis techniques (e.g. dependency analysis, taint analysis, slicing, etc.) assist programmers in narrowing down the scope of responsibility, but none of them can explicitly identify the responsible entity. Meanwhile, the causality analysis is generally not pertinent for analyzing programs, and the structural equations model (SEM) of actual causality misses some information inherent in programs, making its analysis on programs imprecise. In this paper, a novel definition of responsibility based on the abstraction of event trace semantics is proposed, which can be applied in program security and other scientific fields. Briefly speaking, an entity is responsible for behavior B, if and only if R is free to choose its input value, and such a choice is the first one that ensures the occurrence of B in the forthcoming execution. Compared to current analysis methods, the responsibility analysis is more precise. In addition, our definition of responsibility takes into account the cognizance of the observer, which, to the best of our knowledge, is a new innovative idea in program analysis.

Original languageEnglish (US)
Title of host publicationStatic Analysis - 26th International Symposium, SAS 2019, Proceedings
EditorsBor-Yuh Evan Chang
PublisherSpringer
Pages368-388
Number of pages21
ISBN (Print)9783030323035
DOIs
StatePublished - 2019
Event26th International Static Analysis Symposium, SAS 2019 held as part of the 3rd World Congress on Formal Methods, FM 2019 - Porto, Portugal
Duration: Oct 8 2019Oct 11 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11822 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Static Analysis Symposium, SAS 2019 held as part of the 3rd World Congress on Formal Methods, FM 2019
CountryPortugal
CityPorto
Period10/8/1910/11/19

Keywords

  • Abstract interpretation
  • Causality
  • Dependency
  • Program security
  • Responsibility
  • Static analysis

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Responsibility Analysis by Abstract Interpretation'. Together they form a unique fingerprint.

  • Cite this

    Deng, C., & Cousot, P. (2019). Responsibility Analysis by Abstract Interpretation. In B-Y. E. Chang (Ed.), Static Analysis - 26th International Symposium, SAS 2019, Proceedings (pp. 368-388). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11822 LNCS). Springer. https://doi.org/10.1007/978-3-030-32304-2_18