Semantic-based execution model for multilevel secure workflows

Workflow management systems (WFMS) support the modeling and coordinated execution of processes within an organization. To coordinate the execution of the various activities (or tasks) in a workflow, task dependencies are specified among them. As advances in workflow management take place, they are also required to support security. In a multilevel secure (MLS) workflow, tasks may belong to different security levels. Ensuring the dependencies from the tasks at higher security levels to those at lower security levels (high-to-low dependencies) may compromise security. In this paper, we consider such MLS workflows and show how they can be executed in a secure and correct manner. Our approach is based on semantic classification of the task dependencies that examines the source of the task dependencies. We classify the high-to-low dependencies in several ways: conflicting versus conflict-free, result-independent versus result-dependent, strong versus weak, and abortive versus non-abortive. We propose algorithms to automatically redesign the workflow and demonstrate that only a small subset among all the types of high-to-low dependencies requires to be executed by trusted subjects and all other types can be executed without compromising security. The solutions proposed in this paper are directly applicable to another relevant area of research - execution of multilevel transactions in multilevel secure databases since the atomicity requirements and other semantic requirements can be modeled as a workflow. When compared to the research in this area, our work (1) is more general in the sense that it can model several other types of dependencies thereby allowing one to specify relaxed atomicity requirements and (2) is capable of automatically redesigning a workflow without requiring any human intervention by eliminating some cycles among task dependencies, which helps to attain higher degree of atomicity.