Automatic Composition of Secure Workflows

Automatic goal-driven composition of information processing workflows, or workflow planning, has become an active area of research in recent years. Various workflow planning methods have been proposed for automatic application development in systems like Web services, stream processing and grid computing based on compositional architectures. Significant progress has been made on the development of composition methods and on the definition of composition rules. The composition rules can be specified based on the schema, interface and semantics-driven compatibility of processes and data. More importantly, in many practical applications the workflows must be executed under access control policies. In this paper we introduce and study the problem of workflow planning under the constraints of MLS and the Bell-LaPadula model. This problem arises in the context of our implementation of a large-scale stream processing system that can process a wide variety of different inquiries submitted by end users. Extending well-known results from AI planning literature, we first show that under certain simplifying assumptions the workflows satisfying Bell-LaPadula model constraints can be constructed in linear time. Further we show that the problem becomes NP-complete once the use of trusted downgraders for data declassification is allowed. Next, we identify a number of special conditions under which the workflows can still be constructed in polynomial time, even when the use of downgraders is allowed. Finally, we analyze the impact of Chinese Wall constraints on the complexity of the composition problem, and describe an efficient algorithm for composing workflows under these constraints. The proposed approach can be used with any lattice-based access control policies, including Biba integrity model.

By: Marc Lelarge; Zhen Liu; Anton Riabov

Published in: RC23996 in 2006


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .