Segregation of Duties, also called Separation of duties (SoD) has been in the headlight of public accounting firms since the beginnings of the Sarbanes-Oxley regulations, specifically the 404 section. Wikipedia describes it as: “the concept of having more than one person required to complete a task. It is alternatively called segregation of duties or, in the political realm, separation of powers”.

Translated to application security this means that no person should have a set of authorizations that enables them to perform two incompatible tasks of a process. The easiest example is related to the procurement process: The person creating a Purchase Order should not be the same doing the Goods Receipt and another one should be doing the Invoice Receipt. Depending on the size of the company the process could be further splitted into who is doing the Invoice Receipt and the one doing the Payment run.

Such infamous lists of SODs are normally given to companies by their auditors and they are all very similar (From my experience working at PwC and Deloitte). Companies or the auditors then run some automatic programs to analyze the state of authorizations in certain critical systems such as SAP in comparison to these SOD requirements. They normally get “sexy” excel sheets lists with ten thousands of conflicts, and start cleaning up in an iterative process until the auditor is happy.

In 2003 however I was confronted by a client with a completely different approach. We were in a big-bang project that was completely reimplementing the client business models, processes, organization and implementing a new centralized SAP system. I was in charge of the Process and Security team which was covering SOX 404 compliance, the implementation of a new internal control framework and sap security. The head of the shared services department came to me:

*“Greg, I can setup the shared service center to be segregation of duties clean from day 1 of operations. I have received this list from the auditor, how many groups would I need for implementing all SOD rules?”*

You have to imagine those lists as being like 300-400 lines long with entries like this:

(PR-1) Purchase Orders # (PR-2) Goods Receipt

(PR-3) Invoice Receipt # (PR-2) Goods Receipt

(MD-1) Bank Master Data # (PR-1) Purchase Orders

over all areas of business, from finance to sales. What the client was asking me was: Given this list of 300-400 rules, what is the minimum number of people we would need to avoid all segregation of duties problems?* (For the expert: I am simplifying the problem here, clearly you would try to use mitigating controls in real life and not solve everything through organizational changes)*.

After some thinking about the problem I was quite happy to have been attentive during the theoretical computer science lessons at university. Turns out that what the client was asking me was in fact equivalent to a well known problem called “Vertex Coloring”. Unfortunately the problem is one of the so-called NP-complete problems. Finding th smallest group of people satisfying all SOD constraints is equivalent to finding the smallest number of colors needed to color a graph G: this is called its chromatic number. How do we transform one problem into the other one? Turns out it is quite straightforward: Imagine tasks like “creating purchase orders” as vertices of graphs and when 2 tasks are in conflict they are connected by an edge. Based on the previous list, we have a graph representation (See Image)

Finding the chromatic number of a graph

With only those 3 SOD rules to satisfy we would just need 2 groups of people. For small graphs it is quite easy to find an optimal solution, but for graphs with 50 or 60 vertices and 300-400 edges the complexity explodes. I had a special program (Mathematica) run a whole night without finishing. Fortunately there are so called randomized algorithms coming to our rescue. They can find approximate solutions in a short time frame. They do not guarantee to find the optimal solution, but can often guarantee for example that the found solution is not more than twice as worse as the optimal solution. So I ran the randomized program and waited for a solution.

Part 2 of the blog in the next days …