BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Adaptive Resolution of Information Flow Constraints - Santanu Dash
 \, University of Hertfordshire
DTSTART:20130604T134500Z
DTEND:20130604T143000Z
UID:TALK45675@talks.cam.ac.uk
CONTACT:Simon Moore
DESCRIPTION:Information Flow Analysis (IFA) is an indispensable tool in\na
 scertaining whether programs obey a pre-defined security policy.\nThe poli
 cy is typically described as a lattice of privilege\nlevels and the first 
 step towards to IFA is to use annotated\ntypes that hold these privilege l
 evels for expressions. For\nunannotated expressions\, the type system repr
 esents privilege\nlevels as variables\, derives a set of constraints on th
 ese\nvariables and checks the satisfiability of these constraints\nagainst
  the policy lattice. In this talk\, we discuss bottlenecks\nfor generating
  and resolving these constraints for the\npolymorphic lambda calculus and 
 present solutions for mitigating\nthese bottlenecks. We first discuss how 
 the introduction of\nuniversal quantification creates a need for constrain
 t\nsimplification - a computationally expensive operation. Then\, we\ndisc
 uss how operations on the policy lattice like meet and join\noperators con
 tribute significantly to computational costs of the\nresolution process. W
 e highlight the innate relationship between\nboth these issues and the tra
 nsitive closure of Directed Acyclic\nGraphs (DAGs). Finally\, we present a
 n adaptive approach for both\nconstraint simplification and answering latt
 ice queries. The\nadaptive nature of our approach ties the computational c
 osts to\nthe incidence of non-tree edges in the flow-constraint-graph /\ns
 ecurity-lattice. Therefore\, our approach seamlessly scales the\nperforman
 ce graph between the best reported algorithms for trees\nand those for DAG
 s thereby achieving near-linear time complexity\nfor sparse flow-constrain
 t-graphs / security-lattices as opposed\nto traditional approaches which h
 ave cubic time complexity.\n
LOCATION:SS03\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR