Fundamenta Informaticae - Volume 185, issue 4

Authors: Abhishek, Kunal | Dharma Prakash Raj, E.George

Article Type: Research Article

Abstract: An operating system kernel uses cryptographically secure pseudorandom number generator (CSPRNG) for creating address space layout randomization (ASLR) offsets to protect memory addresses of processes from exploitation, storing users’ passwords securely and creating cryptographic keys. However, at present, popular kernel CSPRNGs such as Yarrow, Fortuna and /dev/(u)random which are used by MacOS/iOS/FreeBSD, Windows and Linux/Android kernels respectively lack the very crucial property of non-reproducibility of their generated bitstreams which is used to nullify the scope of predicting the bitstream. This paper proposes a CSPRNG called Cryptographically Secure Pseudorandom Number Generator for Kernel Applications (KCS-PRNG) which generates non-reproducible bitstreams. The proposed …KCS-PRNG presents an efficient design uniquely configured with two new non-standard and verified elliptic curves and clock-controlled Linear Feedback Shift Registers (LFSRs) and a novel method to consistently generate non-reproducible random bitstreams of arbitrary lengths. The generated bitstreams are statistically indistinguishable from true random bitstreams and provably secure, resilient to important attacks, exhibits backward and forward secrecy, exhibits exponential linear complexity, large period and huge key space. Show more

Keywords: Random Number Generator, CSPRNG, LFSR, Elliptic Curve, Kernel Applications

DOI: 10.3233/FI-222111

Citation: Fundamenta Informaticae, vol. 185, no. 4, pp. 285-311, 2022

Authors: Geuvers, Herman | Nederpelt, Rob

Article Type: Research Article

Abstract: The ‘mathematical language’ Automath, conceived by N.G. de Bruijn in 1968, was the first theorem prover actually working and was used for checking many specimina of mathematical content. Its goals and syntactic ideas inspired Th. Coquand and G. Huet to develop the calculus of constructions, CC ([1]), which was one of the first widely used interactive theorem provers and forms the basis for the widely used Coq system ([2]). The original syntax of Automath ([3, 4]) is not easy to grasp. Yet, it is essentially based on a derivation system that is similar to the Calculus of Constructions (‘CC’). …The relation between the Automath syntax and CC has not yet been sufficiently described, although there are many references in the type theory community to Automath. In this paper we focus on the backgrounds and on some uncommon aspects of the syntax of Automath. We expose the fundamental aspects of a ‘generic’ Automath system, encapsulating the most common versions of Automath. We present this generic Automath system in a modern syntactic frame. The obtained system makes use of λD, a direct extension of CC with definitions described in [5]. Show more

DOI: 10.3233/FI-222112

Citation: Fundamenta Informaticae, vol. 185, no. 4, pp. 313-336, 2022

Authors: Kutrib, Martin | Malcher, Andreas | Mereghetti, Carlo | Palano, Beatrice

Article Type: Research Article

Abstract: An iterated uniform finite-state transducer (IUFST ) runs the same length-preserving transduction, starting with a sweep on the input string and then iteratively sweeping on the output of the previous sweep. The IUFST accepts the input string by halting in an accepting state at the end of a sweep. We consider both the deterministic (IUFST ) and nondeterministic (NIUFST ) version of this device. We show that constant sweep bounded IUFSTs and NIUFSTs accept all and only regular languages. We study the state complexity of removing nondeterminism as well as sweeps on constant sweep bounded NIUFSTs , …the descriptional power of constant sweep bounded IUFSTs and NIUFSTs with respect to classical models of finite-state automata, and the computational complexity of several decidability questions. Then, we focus on non-constant sweep bounded devices, proving the existence of a proper infinite nonregular language hierarchy depending on the sweep complexity both in the deterministic and nondeterministic case. Though NIUFSTs are “one-way” devices we show that they characterize the class of context-sensitive languages, that is, the complexity class DSpace (lin). Finally, we show that the nondeterministic devices are more powerful than their deterministic variant for a sublinear number of sweeps that is at least logarithmic. Show more

Keywords: Iterated transducers, nondeterminism, descriptional complexity, sweep complexity, language hierarchies

DOI: 10.3233/FI-222113

Citation: Fundamenta Informaticae, vol. 185, no. 4, pp. 337-356, 2022

Authors: Lin, Cheng-Kuan | Kung, Tzu-Liang | Hung, Chun-Nan | Teng, Yuan-Hsiang

Article Type: Research Article

Abstract: System diagnosis is process of identifying faulty nodes in a system. An efficient diagnosis is crucial for a multiprocessor system. The BGM diagnosis model is a modification of the PMC diagnosis model, which is a test-based diagnosis. In this paper, we present a specific structure and propose an algorithm for diagnosing a node in a system under the BGM model. We also give a polynomial-time algorithm that a node in a hypercube-like network can be diagnosed correctly in three test rounds under the BGM diagnosis model.

Keywords: system diagnosis, diagnosability, local diagnosis, BGM model, hypercube-like network

DOI: 10.3233/FI-222114

Citation: Fundamenta Informaticae, vol. 185, no. 4, pp. 357-373, 2022