В статье рассматриваются методы анализа программ и описывается практика применения данных методов для автоматизации задачи поиска ошибок в программном обеспечении. Подробно рассмотрен метод динамического анализа программ на основе инструментации, отслеживания потока помеченных данных и генерации наборов условий для автоматического построения входных данных. Рассмотрены особенности проведения подобного анализа для приложений, написанных на языке Java. Приведено описание прототипа инструмента, реализующего описанные подходы, представлены результаты его применения для анализа набора программ на языке Java и оценка полученных результатов.

В статье рассматривается подход к уменьшению времени динамического анализа программ при помощи применения параллельных вычислений при проверке выполнимости ограничений, а также при применении распределенных вычислений в процессе динамического анализа программ. Приводятся результаты практического применения данного подхода, реализованного в рамках инструмента динамического анализа Avalanche. На основе полученных результатов даётся оценка увеличения эффективности динамического анализа и рассматриваются возможности дальнейшего развития разработанных методов.

В статье рассмотрена возможность совмещения автоматического рефакторинга с обнаружением повторяющихся фрагментов исходного кода для программ на языках C/C++. Предложена классификация программных клонов с точки зрения дальнейшего применения к ним автоматического рефакторинга. Для каждого выделенного типа клонов описан способ их поиска. Приведены недостатки существующих инструментов и показано, что предложенные методы работают корректно в рассмотренных ситуациях. Подход, описанный в статье, реализован в рамках инструмента Klocwork inSight.

В данной работе описывается расширение языка KAST для решения задачи трансформации исходного кода. В настоящее время язык KAST используется для поиска поддеревьев заданного в виде шаблона вида в синтаксических деревьях, построенных по коду на языках C/C++, Java и C#. В статье также рассматриваются некоторые существующие подходы к трансформации исходного кода и показываются преимущества использования для решения данной задачи языка KAST. Описывается метод, при помощи которого изменения в синтаксическом дереве преобразуются в изменения исходного кода.

Статья посвящена обнаружению дефектов в коде, написанном на динамических языках программирования. Производится обзор статических анализаторов программ на языках Python, Ruby и JavaScript. Показывается, что большинство существующих средств не в состоянии обнаруживать целый класс дефектов: ошибки несоответствия типов. Даётся определение таких ошибок, приводятся данные о том, что они весьма распространены, а также критичны по мнению разработчиков программ. Предлагается подход к выводу типов для динамических языков, а также к реализации обнаружителей дефектов на его основе. Вводится понятие трассы дефекта, описывается построение такой трассы.

При статической верификации драйверов устройств операционной системы Linux необходимо учитывать особенности взаимодействия драйверов с сердцевиной ядра, так как это взаимодействие оказывает определяющее влияние на работу драйвера. В то же время, верификации драйвера в комбинации с исходным кодом сердцевины ядра не представляется возможной ввиду сложности и объема получающегося кода. В качестве решения этой проблемы в статье предлагается метод моделирования окружения драйверов на основе П-исчисления Р.Милнера и метод трансляции П-модели окружения в программу на языке Си, которая при связывании с исходным кодом драйвера описывает с точки зрения инструментов статической верификации те же сценарии работы драйвера, что и реальное окружение драйвера в операционной системе.

Эта статья описывает усовершенствованные алгоритмы лексической оптимизации запросов. Алгоритмы обнаруживают и удаляют избыточные условия из ограничения запроса, чтобы упростить его. Cтатья также представляет результаты применения этих оптимизационных техник и их влияние на скорость обработки запроса.

Статья посвящена развитию метода декомпозиции для индексации, поиска и анализа больших пространственных данных. Главное внимание уделяется алгоритмам, основанным на регулярных октальных деревьях и обеспечивающим эффективное решение ряда вычислительных задач. Исследуемые алгоритмы определения столкновений и выборки по заданной области, в частности, применимы для моделирования сложных динамических пространственно-трехмерных сцен с объектами, имеющими протяженные границы. Для модельного набора данных на основе вероятностного анализа выводятся оценки сложности, которые обобщают и улучшают известные результаты и служат теоретическим обоснованием для применения алгоритмов к более широкому классу приложений.

В статье описывается способ распознавания предметно-специфичных терминов, которые присутствуют в текущей базе знаний, но выражают отсутствующие в ней концепты. Разработанный метод может быть применен к неформальным базам знаний, поскольку требует только вычисления семантической близости между концептами и статистики встречаемости терминов в корпусе документов. Экспериментальная проверка показывает, что разработанный алгоритм превосходит существующие подходы, а также позволяет повысить точность разрешения лексической многозначности.

При заполнении полей профиля в различных интернет-сервисах пользователи зачастую по ошибке или преднамеренно не указывают значения некоторых демографических атрибутов, таких как пол, возраст, семейное положение, уровень образования, религиозные и политические взгляды. Вместе с тем, информация об атрибутах пользователей позволяет существенно повысить эффективность систем рекомендации, интернет-маркетинга и других приложений, предполагающих персонализацию результатов. В статье предлагается метод автоматического определения демографических атрибутов пользователей социального сервиса микроблогов Twitter по текстам их сообщений и другой доступной информации из профилей. Метод основан на алгоритме машинного обучения, его отличительными особенностями являются полностью автоматическое построение исходного набора данных для обучения и тестирования, а также поддержка широкого набора языков и демографических атрибутов. Экспериментальные исследования показали высокое качество результатов определения пола, возраста и семейного положения пользователя для наиболее популярных языков: английского, русского, немецкого, французского, итальянского и испанского. Кроме того, для английского языка поддерживается также определение уровня образования, а также религиозных и политических взглядов пользователя.

Описан и обоснован алгоритм нахождения решения системы алгебраических уравнений над полем k для идеалов нулевой размерности, в случае если задан базис Гребнера идеала этой системы для лексикографического порядка на термах от ее переменных. Полученное решение лежит в алгебраическом замыкании основного поля. Приведен пример системы алгебраических уравнений, имеющей единственное решение в основном поле, а общее число решений экспоненциально относительно описания этой системы.

В работе представлена постановка задачи оптимального упорядочения конфликтующих объектов и ее связь с задачей коммивояжера (Travelling Salesman Problem или TSP). Задача оптимального упорядочения конфликтующих объектов возникает в социологии, при анализе графов в социальных сетях, при размещении рекламных заказов в сетях СМИ. В статье описаны используемые авторами на практике быстрые алгоритмы решения этой и связанных с ней задач. Также рассмотрена задача TSP с разреженной матрицей штрафов. Для задач TSP с ленточной и блочно-диагональной матрицами найдены необходимые и достаточные условия и построены точные алгоритмы, при которых достигается нулевое минимальное значение целевой функции задачи. Предложены эффективные алгоритмы и для произвольных разреженных матриц. Приведены результаты аналитических и численных исследований сложности разработанных алгоритмов и точности решения, а также рекомендации по применению алгоритмов для решения задач подобного типа.