Search for: All records

By exploiting symmetries of finite fields, covering perfect hash families provide a succinct representation for covering arrays of index one. For certain parameters, this connection has led to both the best current asymptotic existence results and the best known efficient construction algorithms for covering arrays. The connection generalizes in a straightforward manner to arrays in which every t-way interaction is covered λ > 1 times, i.e., to covering arrays of index more than one. Using this framework, we focus on easily computed, explicit upper bounds on numbers of rows for various parameters with higher index. 

Detecting arrays provide test suites for complex engineered systems in which many factors interact. The determination of which interactions have a significant impact on system behaviour requires not only that each interaction appear in a test, but also that its effect can be distinguished from those of other significant interactions. In this paper, compact representations of detecting arrays using vectors over the finite field are developed. Covering strong separating hash families exploit linear independence over the field, while the weaker elongated covering perfect hash families permit some linear dependence. For both, probabilistic analyses are employed to establish effective upper bounds on the number of tests needed in a detecting array for a wide variety of parameters. The analyses underlie efficient algorithms for the explicit construction of detecting arrays. 

For a finite field of order.q, and.v a divisor of.q − 1, additive translates of a cyclotomic vector yield a.q × q cyclotomic array on.v symbols. For every positive integer.t, for certain.q sufficiently large with respect to.v, such a cyclotomic array is always a covering array of strength.t. Asymptotically such arrays have far too many rows to be competitive with certain other covering array constructions. Nevertheless, for small values of .t , this cyclotomic method produces smallest known covering arrays for numerous parameters suitable for practical application. This paper extends these ideas and shows that cyclotomy can produce covering arrays of higher index, and locating and detecting arrays with large separation. Computational results also demonstrate that certain cyclotomic arrays for the same order.q but different values of .v can be juxtaposed to produce mixed-level covering, locating, and detecting arrays. 

Attribute-based methods are inherently identity-less as authorization decisions are made in terms of attributes possessed by the subject rather than identity. However, anonymity against the system is not guaranteed when attribute distribution allows for the composition of a policy that few subjects can satisfy. An anonymizing array ensures that any assignment of values to t attributes that appears in the array appears at least r times. When an anonymizing array is used for subjects registered to a system and policies contain conjunctions of at most t attributes, the system cannot identify the subject using the policy to to gain authorization with greater than 1𝑟 probability. Anonymizing arrays are similar to covering arrays with higher coverage and constraints, but have an additional desired property, homogeneity, due to their application domain. In this paper, we develop constructions for anonymizing arrays and propose a post-optimization mechanism to reduce homogeneity. 

Locating arrays are designs used in combinatorial testing with the property that every set of d t-way interactions appears in a unique set of tests. Using a locating array to conduct fault testing ensures that faulty interactions can be located when there are d or fewer faults. Locating arrays are fairly new and few techniques have been explored for their construction. Most of the available work is limited to finding only one fault. Known general methods require a covering array of strength t+d and produce many more tests than are needed. We present Partitioned Search with Column Resampling (PSCR), a randomized computational search algorithmic framework to verify if an array is (d t)-locating by partitioning the search space to decrease the number of comparisons. If a candidate array is not locating, random resampling is performed until a locating array is constructed or an iteration limit is reached. Results are compared against known locating array constructions from covering arrays of higher strength and against published results of mixed level locating arrays for parameters of real-world systems. The use of PSCR to build larger locating arrays from a variety of ingredient arrays is explored. 

Locating arrays (LAs) are experimental designs for screening interactions in engineered systems. LAs are often highly unbalanced, requiring advanced techniques to recover the terms that significantly influence system performance. While perfect recovery is achieved in the absence of noise, real systems are noisy. Therefore, in this paper, we study the robustness of recovery in the presence of noise. Using known models to generate synthetic data, we investigate recovery accuracy as a function of noise. Separation is introduced into LAs to allow more coverage for each t-way interaction; when separation is higher, recovery in noisy scenarios should improve. We find that locating arrays are able to recover the influential terms even with high levels of noise and that separation appears to improve recovery. Under the pessimistic assumption that noise depends on the range of responses, it is no surprise that terms with small coefficients become indistinguishable from noise. 

Determining correctness and performance for complex engineered systems necessitates testing the system to determine how its behaviour is impacted by many factors and interactions among them. Of particular concern is to determine which settings of the factors (main effects) impact the behaviour significantly. Detecting arrays for main effects are test suites that ensure that the impact of each main effect is witnessed even in the presence of d or fewer other significant main effects. Separation in detecting arrays dictates the presence of at least a specified number of such witnesses. A new parameter, corroboration, enables the fusion of levels while maintaining the presence of witnesses. Detecting arrays for main effects, having various values for the separation and corroboration, are constructed using error-correcting codes and separating hash families. The techniques are shown to yield explicit constructions with few tests for large numbers of factors.