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.