A Fixpoint Calculus for Local and Global Program Flows

A Fixpoint Calculus for Local and Global Program Flows

Languages of nested trees Swarat Chaudhuri University of Pennsylvania (with Rajeev Alur and P. Madhusudan) Automata-theoretic, branching-time model-checking Abstraction (FSM, boolean program) Specification tree automaton Tree unfolding Model Abstraction: boolean programs checker(or pushdown systems) Yes/No

Specification: finite-state tree automata? Tree automata Set of states: Initial state: Transitions: Acceptance: final state, Buchi, parity Closed under union, intersection, projection, complement Emptiness Typical property: if A holds now, then along

some and model-checking decidable Equivalent path, B holds later. to MSO; bisimulation-closed version captures mu-calculus Tree automata and pre/postconditions if A holds at a call, then along some path, B holds at the matching return. main A

foo call call ret ret B If you use pushdown tree automata, you get undecidability Basic primitive, intrinsic to real software specification languages Logic and automata: foundations for specifications Theory lagging behind practice?

Our contributions Pre/post-conditions Interprocedural dataflow involving local Regular + global variables languages Stack inspection mu-calculus = Tree automata of nested

trees Local, context-sensitive reachability Alternating automata on nested trees = Mu-calculus on nested trees (NT-mu) Model-checking algorithm matches CTL in complexity (EXPTIME) Boolean program: tree unfolding x = true; foo

bar(); call bar if (*) y = false; else x = true; return y; bar return return

return Trees are infinite in general Nested trees foo call Instead obtained augmenting ATodag of making trace global by path,

aacceptors tree with stronger, follow treejump-edges edges why not Jump-edges are nested add more structure to the modeling programs, While Tomodel?

trace local path, follow jump-edges to summary jump-edgesmap across edges procedure calls bar return return return

Infinite in general Nested trees Infinite in general Finite automata on nested trees Set of states: Initial state: Transitions: Transitions distinguish between call, local and return nodes State at return node depends on states at both parents

Acceptance: final state, Buchi, parity Local reachability main entry entry Stack inspection: if foo is to be called along some path, then all methods on stack must be privileged. Expression expr(g,l), where g is global and l is local, is very busy. p is reachable in the main context. Model-checking

Pushdown system Nested tree automaton Nested tree Model Solution for trees: take product; reduce to checker pushdown game Yes/No Solution for nested trees: take product; reduce to pushdown game

Model-checking: product Stack of program synchronized with implicit stack of automaton Conditions on left and right branch must both hold Reduces to pushdown game Complexity: EXPTIME-complete Complexity of CTL: EXPTIME-complete Alternating reachability: EXPTIME complete Properties of nondeterministic nested tree automata Closed under union, projection. Closed under intersection (product as in tree automata; implicit stacks are synchronized).

Emptiness in EXPTIME. Not closed under complement. Solution: alternation. Alternating automata on nested trees Acceptance a game between the automaton and an adversary. Tree accepted iff automaton has a winning strategy. Trivially closed under boolean operations. For automata on nested trees, terms such as Model-checking: product still leads to a pushdown Thus, oftop

cost. [If game. the left child is aalternation return node comes and q1 isfree at the of the stack at the current point in the game, then pop the stack and move to state q2.Emptiness: Left subtree undecidable. accepted with new configuration.] More expressive than

nondeterministic automata; different in flavor from tree logics. A mu-calculus on nested trees [POPL 2006] call s v u local ret ret

p local Jump edges let us chop a nested tree into subtrees that summarize contexts. Mu-calculus interpreted on summary trees. The logic NT-mu Fixpoints over summary trees Captures fixpoint computation for pushdown games. One-step local reachability call

ret Expressive equivalence Theorem: Bisimulation-closed alternating parity automata on nested trees and NT-mu have the same expressiveness. Corollary: NT-mu can capture every property that the mucalculus can. Corollary: The temporal logic CARET is contained in NTmu. Corollary: Satisfiability of NT-mu is undecidable. Most expressive temporal logic for which software model-checking is theoretically (Note: Even monadic

feasible. second-order logic on trees has decidable satisfiability.) Monadic second-order logic on nested trees Theorem: Model-checking even the bisimulation-closed fragment of MSO is undecidable. Theorem: Can encode nondeterministic NTAs. Conjecture: Incomparable with alternating NTAs. Our contributions NTA = NT-mu Local, context-sensitive reachability Interprocedural dataflow involving local + global variables

LTL CTL Pre/post-conditions mu-calculus = Stack inspection Tree automata New class of structures called nested trees Logic and automata accepting regular languages of nested trees Model-checking in EXPTIME Expressiveness: analog of connection between NTA, NT-mu: EXPTIME

alternating tree automata and mu-calculus MSO does not seemMu-calculus, interesting CTL, alternating tree automata: EXPTIME Reachability games: EXPTIME Questions Professor Vardi asks Why not use mu-calculus + abstract edge? Cannot relate the path till the matching return with the path after the matching return. Effect: plucking the structure at the join-node and making a clone

Resultant logic may be embedded into the tree and therefore MSO on trees. Hence decidable satisfiability. Questions Why is emptiness undecidable? You can encode Posts correspondence problem. Using the stack, you can ensure that the orders of dominoes are the same. Using alternation/branching, check that their conjunctions are the same word. Why is MSO model checking undecidable? Existential quantification in this world is hopeless. You can pick out a structure from the full tree that can encode the undecidability of alternating NTA emptiness. A truly branching property

call call p p ret ret All path fragments through a context agree on state of specification automaton: If p is seen between a call and one of its matching returns, then p is seen between that call

and all of its matching returns. Questions Is branching really needed? Dataflow analysis = branching time model checking. Comparing paths in a procedure. Is this practical? I cannot hear you. Have you implemented this? We are currently implementing a checker for Java stack inspection properties on top of IBMs Java bytecode analysis infrastructure. Uses subclass of NTAs as specs.

Recently Viewed Presentations

  • Capital Facilities

    Capital Facilities

    Proloquo2Go is a comprehensive, well supported app. Proloquo2Go is probably the most popular communication app. Proloquo2Go contains over 14,000 symbols, and allows you to design communication pages for a wide range of abilities from beginning communicators to literate speakers. Proloquo2Go...
  • Слайд 1 - GiMA

    Слайд 1 - GiMA

    Additional marketing measures at the stands of participants (special promotions, lotteries of companies: Travelsystem, Transaero Airlines (tickets), Australia & Oceania Travel (cash bonuses), Renti Tours with the participation of Astir Palace (trip to Greece), and others).
  • Presentation: Program Overview

    Presentation: Program Overview

    Learning Objectives. After this session, you will be able to— Explain why we should use low tidal volume ventilation (LTVV) Outline the historical background and scientific evidence supporting the use of LTVV
  • Low Carbon Innovation in China Prospects, Politics & Partnerships

    Low Carbon Innovation in China Prospects, Politics & Partnerships

    Not a 'Manhattan project' Profound test for state/market funding, even the entire debate Exceptional dependence on geo-politics Need for international collaboration in innovation International context - economic turbulence; political economic transition; 'global' emergence China and LCI - Policy Significant legislative...
  • Koala By: Maya Oigara Animal Facts Koalas are

    Koala By: Maya Oigara Animal Facts Koalas are

    Life Cycle. Adult koalas do not live with a group they live by themselves. Adult koala live up to13 to 18 years. Adult koala look like there mom. A picture of the animal as a baby or young. adultanimal as...
  • Man Ray

    Man Ray

    An Introduction to Man Ray . Emmanuel Radnitzky. 1890-1976. American visual artist. Painter, Photographer, Filmmaker . Invented Rayographs. Significant contributor to Dada and Surrealist movements but ties to each were informal
  • Deductive vs Inductive Reasoning

    Deductive vs Inductive Reasoning

    Determine the premise and conclusion of a given conditional statement. Rewrite a given conditional statement in standard "if . . ., then . . . form. Rewrite a biconditional as the conjunction of two conditionals. Objectives Determine if two statements...
  • Hierarchical Nanomanufacturing of Carbon Nanotube Sheets and ...

    Hierarchical Nanomanufacturing of Carbon Nanotube Sheets and ...

    (D) The relationships between in-plane and thickness-direction Poisson's ratios for SWNT (black) and MWNT (red) sheets having the force constant ratios R that yield the measured Poisson's ratios (closed circles). The Poisson's ratio changes result from varying the indicated average...