2010-09-14 - the slides from my recent (re-)presentation (with lots of extra bits) at SEC-T 2010, will soon be online! exploit code [...]

2009-12-18 - The slides from my recent presentation at CRESTCon 2009, the 'replacement' for CHECKCon, are now online! exploit code for the demonstrations [...]


basic research is what I am doing when I don't know what I am doing.


  • September 14-10
    - SEC-T 2010: "Vulnerabilities in Full/Virtual Disk Encryption Products"
    Neil Kettle
    Rio theatre, Stockholm, Sweden
    [ presentation (pdf) - abstract ]
  • December 22-09
    - CRESTCon 2009: "[Win32] Full/Virtual Disk Encryption Vulnerabilities"
    Neil Kettle
    15th December, Royal Holloway College, University of London
    [ presentation (pdf) - abstract ]
  • April 19-09
    - CanSec 2009: "Bug classes we have found in *BSD, OS X and Solaris kernels"
    Neil Kettle and Christer Oberg
    Vancouver, Canada
    [ presentation (odp) - presentation (pdf) - abstract ]
  • September 02-08
    - Anytime Algorithms for ROBDD Symmetry Detection and Approximation
    Neil Kettle
    PhD thesis, Computing Laboratory, University of Kent, Canterbury, Kent, CT2 7NF.
    Abstract: Reduced Ordered Binary Decision Diagrams (ROBDDs) provide a dense and memory efficient representation of Boolean functions. When ROBDDs are applied in logic synthesis, the problem arises of detecting both classical and generalised symmetries. State-of-the-art in symmetry detection is represented by Mishchenko's algorithm. Mishchenko showed how to detect symmetries in ROBDDs without the need for checking equivalence of all co-factor pairs. This work resulted in a practical algorithm for detecting all classical symmetries in an ROBDD in $O(|G|^3)$ set operations where $|G|$ is the number of nodes in the ROBDD. Mishchenko and his colleagues subsequently extended the algorithm to find generalised symmetries. The extended algorithm retains the same asymptotic complexity for each type of generalised symmetry. Both the classical and generalised symmetry detection algorithms are monolithic in the sense that they only return a meaningful answer when they are left to run to completion. In this thesis we present efficient anytime algorithms for detecting both classical and generalised symmetries, that output pairs of symmetric variables until a prescribed time bound is exceeded. These anytime algorithms are complete in that given sufficient time they are guaranteed to find all symmetric pairs. Theoretically these algorithms reside in $O(n^3+n|G|+|G|^3)$ and $O(n^3+n^2|G|+|G|^3)$ respectively, where $n$ is the number of variables, so that in practice the advantage of anytime generality is not gained at the expense of efficiency. In fact, the anytime approach requires only very modest data structure support and offers unique opportunities for optimisation so the resulting algorithms are very efficient. The thesis continues by considering another class of anytime algorithms for ROBDDs that is motivated by the dearth of work on approximating ROBDDs. The need for approximation arises because many ROBDD operations result in an ROBDD whose size is quadratic in the size of the inputs. Furthermore, if ROBDDs are used in abstract interpretation, the running time of the analysis is related not only to the complexity of the individual ROBDD operations but also the number of operations applied. The number of operations is, in turn, constrained by the number of times a Boolean function can be weakened before stability is achieved. This thesis proposes a widening that can be used to both constrain the size of an ROBDD and also ensure that the number of times that it is weakened is bounded by some given constant. The widening can be used to either systematically approximate an ROBDD from above (i.e. derive a weaker function) or below (i.e. infer a stronger function). The thesis also considers how randomised techniques may be deployed to improve the speed of computing an approximation by avoiding potentially expensive ROBDD manipulation.
    [ thesis (pdf) - no abstract ]
  • June 17-08
    - Bit-Precise Reasoning with Affine Functions
    Neil Kettle and Andy King
    In 1st International Workshop on Bit-Precise Reasoning (BPR-2008)
    [ paper (pdf) - link - abstract ]
  • August 30-07
    - An Anytime Algorithm for Generalized Symmetry Detection in ROBDDs
    Neil Kettle and Andy King
    IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), IEEE. (Note: Copyright held by IEEE 2007.)
    [ paper (pdf) - link - abstract ]
  • August 10-06
    - Proof of New Decompositional Results for Generalized Symmetries
    Neil Kettle and Andy King
    Technical Report 05-06, Computing Laboratory, University of Kent, Canterbury, Kent, CT2 7NF.
    [ paper (ps) - abstract ]
  • March 20-06
    - Widening ROBDDs with Prime Implicants
    Neil Kettle, Andy King, and Tadeusz Strzemecki
    In Holger Hermanns and Jens Palsberg, editors, 12th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), volume 3920 of Lecture Notes in Computer Science, pages 105-119. Springer-Verlag. (Note: see http://www.springer.de/comp/lncs/index.html.)
    [ paper (ps) - paper (pdf) - presentation (pdf) - link - abstract ]
  • February 16-06
    - Proof of New Implicational Relationships between Generalized Symmetries
    Neil Kettle and Andy King
    Technical Report 13-05, Computing Laboratory, University of Kent, Canterbury, Kent, CT2 7NF.
    [ paper (ps) - abstract ]
  • January 30-06
    - An Anytime Symmetry Detection Algorithm for ROBDDs
    Neil Kettle and Andy King
    In Hidetoshi Onodera, editor, 11th Asia and South Pacific Design Automation Conference (ASPDAC), pages 243-248. IEEE. (Note: Copyright held by IEEE 2006.)
    [ paper (ps) - paper (pdf) - presentation (pdf) - link - abstract ]