This paper provides an overview of program analysis techniques and describes practical implementation of these techniques for automatic software defect detection. The paper focuses on program dynamic analysis technique based on tainted data flow tracing, instrumentation and constraint set construction for automatic input generation. An overview of practical considerations for developing a dynamic analysis tool for Java applications is given. It is complemented by a detailed description of actual prototype implementation created within the scope of this project. Finally, the paper features an overview of practical results obtained on a number of Java applications and provides an evaluation of these results.

This paper focuses on dynamic program analysis optimization through the use of distributed computing scheme and parallel computing for checking satisfiability of Boolean constraint sets. An overview of results obtained from applying the practical implementation of parallel and distributed schemes of dynamic analysis to a number of open-source applications is given. The paper presents a detailed evaluation of the increased efficiency of dynamic analysis achieved while applying developed techniques. Finally, the authors propose a number of possible directions for future work.

The article discusses the possibility to combine automatic refactoring with detection of repeating fragments in C/C++ source code. Classification of clones is proposed in terms of their further use during automatic refactoring. For each clone type the method for detection is described. Shortcomings of existing tools are pointed out and it is shown that proposed method works correctly in considered situations. The approach described in this article has been implemented in Klocwork inSight refactoring tool.

This article is devoted to KAST language extensions introduced for purposes of sources code transformation. Currently KAST is used for matching syntactic patterns in syntactic trees built of C/C++, Java or C# sources. Several existing approaches to code transformation are also considered and KAST advantages over those approaches are highlighted. A method for converting modifications of syntactic trees into modifications of source code is also described.

The paper deals with detection of defects in a program code written in dynamic languages. At first, overview of static analyzers for programs in Python, Ruby and JavaScript is done. After this, the paper shows that most of existing tools are not able to detect entire class of defects: types inconsistency errors. Such errors are defined, the paper proves that the errors are prevailing and rather critical in the opinion of software developers. It presents an approach to type inference for dynamic languages and to implementation of checkers based on output from type inference. Concept of defect trace is introduced and construction of such trace is described then.

In static device driver verification of Linux operating system it is necessary to take into account the specifics of the communication between drivers and kernel core as far as it plays the main role in the drivers’ behavior. At the same time the verification of a driver together with kernel core source code is not feasible due to complexity and size of the resulting source code. As a solution the paper presents the modeling method of driver environment based on R.Milner  calculus and the method of  model translation into C program. Being linked with the driver the resulting program has the same scenarios of driver behavior as the real driver environment in operating system from the static verification tools point of view.

This paper describes enhanced algorisms of query lexical optimization. These algorisms detect and remove redundant conditions from query restriction to simplify it. The paper also presents results of implementation of these optimization techniques and those effects on query processing speed.

This paper is devoted to the elaboration of spatial indexing methods implemented by means of decomposition technique. Special attention is given to decomposition based on regular octrees, which is known to provide efficient solution for collision detection and spatial query problem and being applicable not only to sets of point data, but also to spatially extended objects. Based on probabilistic analysis, complexity estimations are evaluated for model set of data. They generalize previous results and serve as theoretical background to wide practical application of discussed methods.

This paper describes a novel approach for recognition of domain-specific terms that exist in the knowledge base but represent new concepts. Our method can be applied to informal knowledge bases – it requires only semantic similarity between concepts and statistics of terms extracted from the corpus. We show that our method outperforms existing approaches and improves precision of word sense disambiguation algorithm.

Users of internet services often make errors or intentionally provide misleading information about their demographic attributes, including gender, age, marital status, education, religious and political views. At the same time, knowing values of user attributes allows to enhance the performance of recommender systems, internet marketing solutions, and other applications based on personalized results. In the paper, a method is proposed for automatic detection of demographic attributes of Twitter users by analyzing their textual messages and other data from their profiles. The method is based on a machine learning algorithm. Its distinctive features are fully automatic compilation of training and testing data sets as well as support for a broad and extendable range of languages and demographic attributes. Experimental study showed high accuracy of gender, age, and marital status detection for the most popular languages: English, Russian, German, French, Italian, and Spanish. Besides, detection of education, religious and political views is also supported for English.

Described and proved the algorithm for finding some solution of algebraic equations over arbitrary field k for zero dimension ideals if Gröbner basis of this ideal over lexicographic order is given. The found Solution lies in the algebraic closure of k. An example for a system of algebraic equations having a unique solution in the main field, and exponentially many solutions of this system is suggested.

The paper presents the setting of the problem of optimal ordering of conflicting objects related to the Travelling Salesman Problem (TSP). The problem of optimal ordering of conflicting objects appears in sociology, in graph analysis and finding in them optimal paths, in advertising in various media. Solution algorithms are described for this and related problems. The TSP with sparse matrix is also considered. For sparse practice cases of the TSP necessary and sufficient conditions are proved to objective function attained its minimum and the algorithms guaranteeing exact solution are constructed. The practical results of analytical and numerical investigations of algorithm complexity and solution accuracy are presented as well as recommendations for the algorithm applications to the solution of these problems.