publications and online documents

This is a list of documents I have been authoring or co-authoring. The most recent are listed first.

[inline abstracts, outline abstracts]

submitted

Karl Krukow.
- Towards a Theory of Trust for the Global Ubiquitous Computer.
- PhD Thesis, BRICS, University of Aarhus. August, 2006.
- Abstract.
  This dissertation contributes to a relatively young field in computer science research, the field of trust-based security. Primarily, theories of computational trust are considered, i.e., principles, models and associated reasoning techniques. It is argued that one or several theories of trust should constitute a corner-stone in the answer to one of the so-called `Grand Challenges' for computer science research: `Science for Global Ubiquitous Computing.' A central implication is that trust management is not purely an engineering task: To be compatible with the vision of a science for global ubiquitous computing, it must be amenable to rigorous reasoning; hence, mathematical models as well as languages and tools are necessary to achieve the ultimate goal.
  
  The scientific contributions of this dissertation are primarily theoretical, and lie within each of these three areas: We develop mathematical models for trust management, associated domain-specific policy languages as well as tools (in a theoretical sense, e.g., algorithms and operational semantics). At a more practical level, it is shown how a general formal approach to reputation-based trust management has applications in a research area previously not linked to computational trust: A prototype software framework for history-based access control in Java is implemented based on models, languages and tools developed in this dissertation.
- Keywords: [-]
- Download: [pdf]
Karl Krukow and Mogens Nielsen.
- From Simulations to Theorems: A Position Paper on Research in the Field of Computational Trust.
- To be published in Proceedings from for FAST 2006, Springer, 2006.
- Abstract.
  Since the millennium, a quickly increasing number of research papers in the field of ``computational trust and reputation'' have appeared in the Computer Science literature. However, it remains hard to compare and evaluate the respective merits of proposed systems. We argue that rigorous use of formal probabilistic models enables the clear specification of the assumptions and objectives of systems, which is necessary for comparisons. To exemplify such probabilistic modeling, we present a simple probabilistic trust model in which the system assumptions as well as its objectives are clearly specified. We show how to compute (in this model) the so-called predictive probability: The probability that the next interaction with a specific principal will have a specific outcome. We sketch preliminary ideas and first theorems indicating how the use of probabilistic models could enable us to quantitatively compare proposed systems in various different environments.
- Keywords: [Trust, Reputation, Hidden Markov Models, Kullback-Leibler Divergence, Probabilistic Models]
- Download: [pdf]
Karl Krukow, Mogens Nielsen and Vladimiro Sassone.
- A Logical Framework for Reputation Systems and History-based Access Control.
- Journal Version, Submitted.
- Abstract.
  Reputation systems are meta systems that record, aggregate and distribute information about the past behaviour of principals in an application. Typically, these applications are large-scale open distributed systems where principals are virtually anonymous, and (a priori) have no knowledge about the trustworthiness of each other. Reputation systems serve two primary purposes: helping principals decide whom to trust, and providing an incentive for principals to well-behave.
  
  A logical policy-based framework for reputation systems is presented. In the framework, principals specify policies which state precise requirements on the past behaviour of other principals that must be fulfilled in order for interaction to take place. The framework consists of a formal model of behaviour, based on event structures; a declarative logical language for specifying properties of past behaviour; and efficient dynamic algorithms for checking whether a particular behaviour satisfies a property from the language. It is shown how the framework can be extended in several ways, most notably to encompass parameterized events and quantification over parameters. In an extended application, it is illustrated how the framework can be applied for dynamic history-based access control for safe execution of unknown and untrusted programs.
- Keywords: [--]
- Download: [pdf]
- Also, take a look at JavaHBAC a policy-based framework for a history-based security manager for Java applications. This is a prototype framework for Java security managers, based on the theory in the above paper.
Karl Krukow.
- An Operational Semantics for Trust Policies.
- Accepted for the 6th International Workshop on Issues in the Theory of Security (WITS'06), co-located with ETAPS 2006, Vienna, Austria.
- Abstract.
  In the trust-structure framework for trust management, principals specify their trusting relationships in terms of trust policies. In their paper on trust structures, Carbone et al. present a language for such policies, and provide a suitable denotational semantics. The semantics ensures that for any collection of policies, there is always a unique global trust-state, compatible with all the policies, specifying everyone's degree of trust in everyone else. However, as the authors themselves point out, the language lacks an operational model: the global trust-state is a well-defined mathematical object, but it is not clear how principals can actually compute it. This becomes even more apparent when one considers the intended application environment: vast numbers of autonomous principals, distributed and possibly mobile. We provide a compositional operational semantics for a language of trust policies. The operational semantics is given in terms of a composition of I/O automata. We prove that this semantics is faithful to its corresponding denotational semantics, in the sense that any run of the I/O automaton ``converges to'' the denotational semantics of the policies. Furthermore, as I/O automata are a natural model of asynchronous distributed computation, the semantics coincides with an asynchronous algorithm for distributedly computing the trust-state, suitable in the application environment.
- Keywords: [--]
- Download: [pdf ps]
Karl Krukow and Mogens Nielsen.
- Trust Structures: Denotational and Operational Semantics.
- Journal Version of BRICS-RS-05-30, Submitted.
- Abstract.
  A general framework for distributed trust management is presented. The framework is based on the trust structures of Carbone, Nielsen and Sassone: a domain theoretic generalization of Weeks' framework for credential-based trust management systems, e.g., KeyNote and SPKI. Collections of mutually referring trust-policies (``webs'' of trust) are given a precise meaning in terms of an abstract domain theoretic semantics. A complementary concrete operational semantics is provided, using the well-known I/O automaton model. The operational semantics is proved to adhere to the abstract semantics, effectively providing a distributed algorithm allowing principals to compute the meaning of a ``web'' of trust policies. Several techniques allowing sound and efficient distributed approximation of the abstract semantics are presented and proved correct.
- Keywords: [Trust management, Trust Structures, Trust Policies, Denotational and Operational Semantics]
- Download: [pdf]

published

Karl Krukow.
- An Operational Semantics for Trust Policies.
- BRICS Technical report, RS-05-30.
- Abstract.
  In the trust-structure model of trust management, principals specify their trusting relationships with other principals in terms of trust policies. In their paper on trust structures, Carbone et al. present a language for such policies, and provide a suitable denotational semantics. The semantics ensures that for any collection of trust policies, there is always a unique global trust-state, compatible with all the policies, specifying everyone's degree of trust in everyone else. However, as the authors themselves point out, the language lacks an operational model: the global trust-state is a well-defined mathematical object, but it is not clear how principals can actually compute it. This becomes even more apparent when one considers the intended application environment: vast numbers of autonomous principals, distributed and possibly mobile. We provide a compositional operational semantics for a language of trust policies. The operational semantics is given in terms of a composition of I/O automata. We prove that this semantics is faithful to its corresponding denotational semantics, in the sense that any run of the I/O automaton "converges to" the denotational semantics of the policies. Furthermore, as I/O automata are a natural model of asynchronous distributed computation, the semantics leads to an algorithm for distributedly computing the trust-state, which is suitable in the application environment.
- Keywords: [--]
- Download: [pdf]
Karl Krukow, Mogens Nielsen and Vladimiro Sassone.
- A Framework for Concrete Reputation-Systems
  with Applications to History-Based Access Control (Extended abstract).
- 12th ACM Conference on Computer and Communications Security (CCS'05), Hilton Alexandria Mark Center in Alexandria, VA, USA, Nov. 7-11, 2005. Pages 260--269, ACM.
- Abstract.
  In a reputation-based trust-management system, agents maintain information about the past behaviour of other agents. This information is used to guide future trust-based decisions about interaction. However, while trust management is a component in security decision-making, many existing reputation-based trust-management systems provide no formal security-guarantees. In this extended abstract, we describe a mathematical framework for a class of simple reputation-based systems. In these systems, decisions about interaction are taken based on policies that are exact requirements on agents' past histories. We present a basic declarative language, based on pure-past linear temporal logic, intended for writing simple policies. While the basic language is reasonably expressive (encoding e.g. Chinese Wall policies) we show how one can extend it with quantification and parameterized events. This allows us to encode other policies known from the literature, e.g., `one-out-of-k'. The problem of checking a history with respect to a policy is efficient for the basic language, and tractable for the quantified language when policies do not have too many variables.
- Keywords: [--]
- Download: [pdf ps]
- Also, take a look at JavaHBAC a policy-based framework for a history-based security manager for Java applications. This is a prototype framework for Java security managers, based on the theory in the above paper.
Karl Krukow, Mogens Nielsen and Vladimiro Sassone.
- A Framework for Concrete Reputation-Systems.
- BRICS Technical Report, RS-05-23, July 2005, RS series.
- Abstract.
  In a reputation-based trust-management system, agents maintain information about the past behaviour of other agents. This information is used to guide future trust-based decisions about interaction. However, while trust management is a component in security decision-making, few existing reputation-based trust-management systems aim to provide any formal security-guarantees. We describe a mathematical framework for a class of simple reputation-based systems. In these systems, decisions about interaction are taken based on policies that are exact requirements on agents' past histories. We present a basic declarative language, based on pure-past linear temporal logic, intended for writing simple policies. While the basic language is reasonably expressive, we extend it to encompass more practical policies, including several known from the literature. A naturally occurring problem becomes how to efficiently re-evaluate a policy when new behavioural information is available. Algorithms for the various languages are presented along with complexity analyses.
Karl Krukow and Andrew Twigg,
- Distributed Approximation of Fixed-Points in Trust Structures.
- extended abstract of technical report RS-05-6 (2005)
- In Proceedings from the 25th ICDCS, 2005.
- Abstract.
  Recently, Carbone, Nielsen and Sassone introduced the trust-structure framework; a semantic model for trust-management in global-scale distributed systems. The framework is based on the notion of trust structures; a set of ``trust-levels'' ordered by two distinct partial orderings. In the model, a unique global trust-state is defined as the least fixed-point of a collection of local policies assigning trust-levels to the entities of the system. However, the framework is a purely denotational model: it gives precise meaning to the global trust-state of a system, but without specifying a way to compute this abstract mathematical object. This paper complements the denotational model of trust structures with operational techniques. It is shown how the least fixed-point can be computed using a simple, totally-asynchronous distributed algorithm. Two efficient protocols for approximating the least fixed-point are provided, enabling sound reasoning about the global trust-state without computing the exact fixed-point. Finally, dynamic algorithms are presented for safe reuse of information between computations, in face of dynamic trust-policy updates.
- Keywords: [distributed algorithms, fixed points, trust, trust structures, approximation algorithms, dynamic algorithms]
- Download: [pdf ps]
Karl Krukow and Andrew Twigg,
- Distributed Approximation of Fixed-Points in Trust Structures.
- BRICS Technical Report, RS-05-6, February 2005, RS series.
- Abstract.
  Recently, Carbone, Nielsen and Sassone introduced the trust-structure framework; a semantic model for trust-management in global-scale distributed systems. The framework is based on the notion of trust structures; a set of ``trust-levels'' ordered by two distinct partial orderings. In the model, a unique global trust-state is defined as the least fixed-point of a collection of local policies assigning trust-levels to the entities of the system. However, the framework is a purely denotational model: it gives precise meaning to the global trust-state of a system, but without specifying a way to compute this abstract mathematical object. This paper complements the denotational model of trust structures with operational techniques. It is shown how the least fixed-point can be computed using a simple, totally-asynchronous distributed algorithm. Two efficient protocols for approximating the least fixed-point are provided, enabling sound reasoning about the global trust-state without computing the exact fixed-point. Finally, dynamic algorithms are presented for safe reuse of information between computations, in face of dynamic trust-policy updates.
- Keywords: [distributed algorithms, fixed points, trust, trust structures, approximation algorithms, dynamic algorithms]
- Download: [brics.dk/RS/05/6]
Mogens Nielsen and Karl Krukow.
- On the Formal Modelling of Trust in Reputation-Based Systems.
- in, editors J. Karhumäki, H. Maurer, G. Paun and G. Rozenberg, "Theory is Forever: Essays Dedicated to Arto Salomaa", Springer Lecture Notes in Computer Science, 3113, pp.192--204.
- Abstract.
  In a reputation-based trust management system an entity's behaviour determines its reputation which in turn affects its interaction with other entities. We present a mathematical model for trust aimed at global computing environments which, as opposed to many traditional trust management systems, supports the dynamics of reputation-based systems in the sense that trusting relationships are monitored and changes over time, depending on the behaviour of the entities involved. The main contribution is the discovery that the notion of event structures, well studied e.g. in the theory of concurrency, can faithfully model the important concepts of observation and outcome of interactions. In this setting observations are events and an outcome of an interaction is a maximal set of consistent events describing what happened. We also touch upon the problem of transferring trust or behavioural information between contexts, and we propose a generalised definition of morphism of event structures as an information-transfer function.
- Keywords: [Trust, Risk, Reputation, Dempster-Shafer Theory of Evidence, Formal Models, Event Structures, Uncertain Probabilities]
- Download: [pdf ps dvi]
Vinny Cahill, et al.
- Using Trust for Secure Collaboration in Uncertain Environments.
- IEEE Pervasive Computing, vol.2, num 3, pp. 52-61. (2003).
- Abstract. The SECURE project is investigating the design of security mechanisms for pervasive computing based on the human notion of trust. Our work addresses how entities that encounter each other in unfamiliar pervasive computing environments can overcome initial suspicion to allow secure collaboration to take place.
- Keywords: [Computer Security, Trust, Risk, Authentication]
- Download: [on computer.org]
Mogens Nielsen and Karl Krukow.
- Towards a Formal Notion of Trust.
- Proceedings of the 5th ACM SIGPLAN international conference on Principles and Practice of Declarative Programming (PPDP'03), ACM Press.
- Abstract.
  Trust management systems have been proposed as an alternative to traditional security mechanisms in Global Computing. We present some challenges in establishing a formal foundation for the notion of trust, and some preliminary ideas towards a category of trust models.
- Keywords: [Trust, Trust Management Systems, Security, Languages, Theory]
- Download: [pdf ps dvi]

unpublished

Karl Krukow
- On Foundations for Dynamic Trust Management.
- PhD midway progress report (2004).
- Abstract.
  We introduce the term dynamic trust management as a merger of the traditional concept of trust management with the dynamic aspects of reputation: monitoring of entity behaviour and consequently re-evaluation of trusting relationships; as well as allowing uncertain trust values. We present a preliminary mathematical framework which is based on the notion of trust structures. The framework is suitable for expressing trust management systems which allow uncertain trust values, and we are able to instantiate it to obtain many existing systems. We give an axiomatisation of trust structures, and a notion of structure-preserving functions on these, resulting in a category. The interval construction fits in this setting as a functor into our new category, which is part of a coreflection of our category in a category of complete lattices. We present the dynamic trust model of the SECURE project, and show that its trust structure is an instance of our abstract framework. We show how the SECURE notions of observation and outcome can be modelled uniformly as finite configurations of event structures. This allows us to give a general notion of morphisms of event structures, which can be applied for the transfer of trust- or evidence-information between related SECURE contexts. We consider the operational aspects of our framework, displaying and analysing several distributed least-fixed-point algorithms which can be applied in dynamic trust management systems for computing trust values. In the concluding section we reflect on this work and consider possible future research directions.
- Keywords: [Trust, reputation, formal models, dynamic trust management, security, global computing, autonomous decision-making, SECURE project, trust structures, poset intervals, distributed fixed point algorithms, Dempster-Shafer theory of evidence, opinion model, subjective logic, event structures]
- Download: [pdf ps]