Mathematical Auditing Of Email Broadcasts

R Glen Cooper

Overview

• CIRCULARITY

• REDUNDANCY

How the scripts work

What a difference a picture makes!

Now it's easy to see why 9 (Marketing) eventually re-directs mail back to itself and why 16 (accounts) always gets multiple emails sent to 10 (SALES). For some reason ADMIN (11) wasn't aware that SALES was already re-directing emails to accounts (and other addresses). For many organizations there could be hundreds of re-directions from a single email, which is why manual tinkering is ineffective.

To diagnose these pictures, let's view them as directed graphs where the above problems can be formulated in a natural way. For an overview of graphs, see

/*
Script:	Circularity test for email lists 
Platform: SQL Server 2005
Purpose: This script accepts a table of email 
	re-directions and determines if 
	circularity exists.
	Redirections are represented by a table called Edge
	whose columns LHS and RHS represent the left and 
	right-hand sides of a re-direction.
Output: List of re-directions containing all circular paths
Comment: This test will destroy Edge, so a working copy is used
*/

-- No counting
SET NOCOUNT OFF

-- Make working copy of Edge
IF  EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[dbo].[EdgeTemp]') AND type in (N'U'))
	DROP TABLE [dbo].[EdgeTemp]
SELECT LHS, RHS INTO EdgeTemp FROM Edge
CREATE INDEX NDX_EdgeTemp_RHS ON EdgeTemp(RHS)

-- Recursively delete edges whose RHS vertices have out-degree = 0.
-- Note that the RHS of such edges will disappear from Edge.
-- So will the LHS of such edges if they have out-degree = 1.
-- Note that @@ROWCOUNT = 0 at this point.
DELETE	
FROM EdgeTemp
WHERE RHS NOT IN (SELECT DISTINCT LHS FROM EdgeTemp)
-- If @@ROWCOUNT > 0 at this point, then continue
WHILE @@ROWCOUNT > 0
	DELETE
	FROM EdgeTemp
	WHERE RHS NOT IN (SELECT DISTINCT LHS FROM EdgeTemp)

-- Original graph will have no circular paths 
-- if and only if there are no remaining edges
-- in its working copy.
-- All edges will have out-degree > 0 at this point.
SELECT * FROM EdgeTemp

-- Drop working table
DROP TABLE EdgeTemp

/*
Script: Redundancy test for email lists 
Platform: SQL Server 2005
Purpose: This script accepts a table of email 
	re-directions and determines if 
	any recipient received multiple emails.
	Redirections are represented by a table called Edge
	whose columns LHS and RHS represent	the left and 
	right-hand sides of a re-direction.
Output: Number of redundant paths between any pair of emails having them			
Note: Assumes no circular paths with re-directions.
	Otherwise, script will go into an infinite loop.
	Use sister script to check this beforehand.
*/

-- No counting
SET NOCOUNT ON

-- Determine redundant paths between any pair of emails, and count them
;WITH Collect AS 
( 
-- Collect the LHS and RHS of all paths of length L = 1 (i.e. all edges).
-- Use i to record iteration for diagnostics.
SELECT i= 1, LHS, RHS
FROM Edge
UNION ALL	-- Must use ALL because duplicates will always represent different paths 
-- Collect the LHS and RHS all paths of length L 
-- by joining re-directions with previously collected paths
-- in the collection of length L - 1 
SELECT i = i + 1, Edge.LHS, Collect.RHS
FROM Edge INNER JOIN Collect
ON Edge.RHS = Collect.LHS
)
-- Output result.
-- Set MAXRECURSION to 0 to allow unlimited recursion.
SELECT LHS, RHS, COUNT(*) AS NumPath FROM Collect GROUP BY LHS,RHS HAVING COUNT(*) > 1 OPTION (MAXRECURSION 100)
-- Diagnostics:
-- SELECT i, LHS, RHS FROM Collect ORDER BY CAST(i AS INT), CAST(LHS AS INT), CAST(RHS AS INT) OPTION (MAXRECURSION 100)

/*
Script: Produce random directed graph 
Platform: SQL Server 2005
Purpose: This script builds a random directed graph called Edge
*/

-- No counting
SET NOCOUNT ON

-- Declarations
DECLARE @Vertex1	INT
DECLARE @Vertex2	INT

-- Create Edge
IF  EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'Edge') AND type in (N'U'))
	DROP TABLE Edge
CREATE TABLE Edge(
	LHS varchar(255),
	RHS varchar(255)
) ON [PRIMARY]

-- Initialise the first vertex
SET @Vertex1 = 0

-- Enumerate all pairs of vertices from 1 to 10, 
-- where the second vertex is less than the first,
-- and create a directed edge with 20% probability
-- on each pair chosen (50% either way for those chosen).
-- Note that higher probabilities will create more edges.
WHILE @Vertex1 < 10	-- Number of vertices to build  
	BEGIN
	SET @Vertex1 = @Vertex1 + 1
	SET @Vertex2 = 1
	WHILE @Vertex2 < @Vertex1
		BEGIN
		-- 20% probability of creating directed edge (i.e. 1 out of 5)
		IF CONVERT(INT, 5*RAND()) = 1	
			-- 50% probability direction goes this way (i.e. 1 out of 2)
			IF CONVERT(INT, 2*RAND()) = 1	
				INSERT INTO Edge(LHS,RHS) VALUES(@Vertex1, @Vertex2)
			ELSE
				-- 50% probability direction goes that way 
				INSERT INTO Edge(LHS,RHS) VALUES(@Vertex2, @Vertex1)					
		SET @Vertex2 = @Vertex2 + 1
		END
	END

-- Index Edge
CREATE INDEX IDX_Edge_RHS ON Edge(RHS)

-- Display graph
SELECT * FROM Edge