A Fast Algorithm for Detecting Second Paths in Database Inference Analysis *

Abstract

This paper presents an approach for detecting potential second-path inference problems in a way that is significantly faster than previous approaches. The algorithm uses a relational database schema and functional dependencies to detect the potential for second-path inferences. The second-path inference problem involves the ability to infer higher classified data from lower classified data within a relational database system using joins. In previous research, this type of inference vulnerability was detected by actually finding a path. The approach presented in this paper does not find the path, but detects the existence of a path by adapting a well known algorithm used in database design to test a relational decomposition for the lossless join property. The original lossless join algorithm has been extended to include subtypes. The paper compares the performance of the new algorithm with that of a conventional path-finding algorithm and shows that the new algorithm is 10 to 14 times faster than the path-finding approach using schemas that range from 33 to 48 relations. The final contribution of the paper is the presentation of an algorithm for automatically classifying the discovered paths into various groups, based on their potential for indicating a significant potential security vulnerability.