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 Web services, stream processing and grid computing. Significant progress has been made 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. Workflows must also satisfy information flow security constraints. In this paper we introduce and study the problem of workflow planning in MLS systems under Bell-LaPadula (BLP) policy, or a similar lattice-based policy, such as Biba integrity model. Extending results from AI planning literature, we show that under certain simplifying assumptions the workflows satisfying BLP constraints can be constructed in linear time. When the policy allows downgraders for data declassification, the problem is NP-complete; nevertheless, with additional assumptions efficient algorithms do exist.