UmbriaLogic Research

Information Technology

Structured Strings

Dr. Colin Hirsch, 2007

Security problems like sql code injection and cross-site scripting vulnerabilities can be traced to the common basic use of plain strings to represent structured data and code. This paper gives an explanation of the issue, and develops and discusses an alternative generic encoding for structured string data that, by adding an appropriate layer of abstraction, is very simple, yet completely eliminates an entire attack vector.

Download brainstorm as PDF.

The prototype implementation, and a summary paper, are currently pending.

Mathematical Logic

Guarded Logics: Algorithms and Bisimulation

Colin Hirsch, Dissertation, 2002

For many practical applications of logic-based methods there is a requirement to balance expressive power against computational tractability. Both identifying decidable sub-classes of first-order logic, and extending modal logic to larger, but nevertheless efficiently solvable languages has been a preeminent goal of research.

The guarded fragment of first-order logic was a successful attempt to transfer key tractability properties of modal, temporal, and description logics to a larger fragment of predicate logic. Besides decidability, guarded logics inherit the finite model property, invariance under an appropriate variant of bisimulation, and other nice model theoretic properties including a decidable fixed-point extension.

The goal of this this work is to gain greater insight into the correspondence between the modal world and the guarded world. In this process, several gaps concerning basic, typically modal, features of guarded logics are closed. Guarded second order logic and guarded relational algebra are developed. A recurring key technique consists of encoding structures and formulae used in the guarded world as their modal counterparts. This enables the transfer of various results, as well as giving greater insight into the nature of guarded logics. Touched subjects include tableau-based decision procedures, mapping action guarded logics, canonisation of structures and model-theoretic characterisation theorems.

Download full text as PDF

The Reliability of Queries

Colin Hirsch, "Diplomarbeit", 1998

The reliability of database queries on databases with uncertain information is studied, on the basis of a probabilistic model for unreliable databases.

While it was already known that the reliability of quantifier-free queries is computable in polynomial time, we show here that already for conjunctive queries, the reliability may become highly intractable. We exhibit a conjunctive query whose reliability problem is complete for FP^#P. We further show, that FP^#P is the typical complexity level for the reliability problems of a very large class of queries, including all second-order queries.

We study approximation algorithms and prove that the reliabilities of all polynomial-time evaluable queries can be efficiently approximated by randomized algorithms.

Finally we discuss the extension of our approach to the more general metafinite database model where finite relational structures are endowed with functions into an infinite interpreted domain; in addition queries may use aggregate functions like in SQL. Our result that reliability problems of first-order queries have complexity FP^#P also holds on this extended model.

Download full text as PDF

(The German "Diplom" is about equivalent to an "M.Sc.".)