Aims: To provide a tool for solving workflow scheduling and Access Control problems.
Background: This project deals with an Access Control problem in Information Security. The workflow satisfiability problem (WSP) asks whether there exists an assignment of authorised users to the steps in a workflow specification, subject to certain constraints on the assignment. This is a problem faced every day by very many large companies.
The problem is computationally intractable in general. However the modern world does not rely so much on the polynomial versus NP-hard distinction (P vs NP). Instead we use the much more nuanced Fixed Parameter Tractability (FPT) landscape. This is when we hope to find some problem characteristic that allows a computationally hard problem to become tractable subject only to limiting a particular parameter.
Recent research, led by researchers in this department, has discovered that the workflow problem, subject to access control restrictions, is indeed FPT in some cases. In this project you will research the theory of fixed parameter tractability and the workflow scheduling problem. You will implement heuristic approaches to solving the problem, and also implement the FPT algorithm for work flow scheduling (the parameter is the number of required steps in a given workflow).
Early Deliverables
Report on Fixed Parameter Tractability and how it is different from the P vs NP tradition, with examples.
About Workflow Scheduling subject to access control: Where it occurs, why it is important and the kinds of constraints and authorisations that are useful.
Report on the analysis of the Fixed Parameter Tractability and the NP-hardness of WSP
Report on various other constraint satisfaction techniques used to solve industrial problems such as SAT and CSP solvers.
Programs: A simple backtracking algorithm, an FPT algorithm for the Vertex Cover problem.
Final Deliverables
The program must have a full object-oriented design, with a full implementation life cycle using modern software engineering principles
The program should have an excellent GUI for experimentation.
The report should include experimental assessment of the FPT algorithm, possibly in comparison with a SAT or CSP solver.
The report will describe the software engineering process involved in generating your software.
The report will describe and analyse your implementation of the backtracking FPT algorithm for solving WSP with user-independent constraints.
Suggested Extensions
Study of the Valued WSP allowing us to provide solutions even when WSP is unsatisfiab
