Автореферат (Метод обнаружения ошибок при работе с памятью на статическом этапе отладки программного обеспечения), страница 3

Например,распределение с помощью оператора new, с последующим освобождением спомощью функции free().Приведённая классификация ошибок при работе с памятью охватывает спектрошибок, наиболее часто возникающих у программистов при работе с оперативнойпамятью, способных критически сказаться на работоспособности систем реальноговремени.Разработанная методика обнаружения ОРП предполагает разделениемножества исследуемых проектов ПО на классы сложности: A – простой; B –11средний; C - сложный проекты (см. табл.

2). Отнесение проекта к одному из классовопределяется числом N стр строк исходного кода.КлассN стрТаблица 2. Классы ПОAB3Nстр ∈ ⎡⎣1,10 ⎤⎦Nстр ∈ (10 ,10 ⎤⎦36CNстр ∈ (106 , ∞ ⎤⎦При построении модели программы для проектов, принадлежащих кклассам A и B, применяется синтаксический анализ с использованием средствкомпиляции, которые позволяют получить доступ к промежуточномупредставлению данных.Для построения модели программы для проектов, принадлежащих к классу C,предлагается использовать упрощенный синтаксический анализатор.После построения модели необходимо вычислить возможные состоянияпрограммы в различных точках ее исполнения.Для проектов, принадлежащих к классу сложности A и B, используется методабстрактной интерпретации.Метод абстрактной интерпретации по принципу работы напоминаеттрадиционную интерпретацию программы.

Традиционный интерпретатор оперируетконкретными значениями переменных, хранящихся в памяти; состояние программыв конкретный момент ее выполнения с точки зрения такого интерпретаторапредставляет собой множество пар (obj, value), где obj- программный объект, а value– его значение. При абстрактной интерпретации состояние программыпредставляется множеством пар (obj, valueset), причем valueset – множествозначений программного объекта.Для проектов, принадлежащих к классу сложности C, применяется методупрощенного анализа потока управления.При использовании алгоритмов анализа значений состояние программыпредставляется в виде множества пар (ячейка памяти, множество допустимыхзначений). В ячейках памяти может располагаться как переменная примитивноготипа, так и элемент массива или поле структуры.Существует два основных вида значений ячеек памяти:•числовые значения, для которых используется интервальный анализ дляпроектов класса сложности A и B.Алгоритмы интервального анализа предназначены для определениявозможных значений переменных числового типа.

Операции над точнымизначениями выполняются в соответствии с правилами того языка, на которомнаписана программа. При анализе ветвлений интервальные значения могутразъединяться с последующим объединении при анализе фи-функций.•указатели, для которых используется анализ указателей.Алгоритмы анализа указателей предназначены для определения возможныхзначений переменных указательного типа и используются для проектов сложностивсех трех классов.12Алгоритмы анализа зависимостей применяются при анализе проектовкласса сложности A и B.Зависимость – определенная связь между значениями двух или несколькихячеек памяти.

При анализе фи-функций происходит пересечение имеющихся вразных ветвях зависимостей.При анализе циклов если количество итераций циклов неизвестно, тоиспользуются следующие способы решения подобной проблемы:1.Для проектов класса A несколько итераций цикла анализируютсяобычным образом, после чего делается попытка выделить «инвариант цикла» ивыполнить последнюю итерацию анализа в обобщенной форме. Инвариантом вданном случае называется утверждение или набор утверждений, справедливых налюбой итерации цикла.2.Для проектов класса B и C выполняется прерывание анализа цикла наитерации с заданным номером (для проекта класса С - 1). Состояние программы навыходе данной итерации переносится на выход цикла.При анализе рекурсивных вызовов для проектов класса A и B принебольшом уровне рекурсии значения формальных параметров необходимо хранитьотдельно для каждого вызова функции.

При большом уровне рекурсии используетсяподход контекстно-нечувствительной аппроксимации: функции анализируютсяодин раз при обобщенном значении формальных параметров и в дальнейшемиспользуется полученный результат.Анализ многопоточных программ производится для проектов класса A. Дляпредставления функций над потоками и выбранными объектами синхронизациииспользуется базис конструкций управления параллельным выполнениемпрограммы. Для привязки конструкций программы к потокам, в которых онивыполняются, конструкции объединяются в блоки программы.

Блок программы множество последовательных конструкций, среди которых отсутствуютмежблоковые конструкции, которыми являются if , фи-функции, init , create , join ,lock , unlock , wait , post и state. Конструкции синхронизации взаимодействуют другс другом с помощью блокировки и освобождения объекта синхронизации спомощью отношений синхронизации.Предложенная методика позволяет обнаруживать ошибки работы с памятью впрограммном обеспечении на статическом этапе отладки за короткое время дляпроектов всех классов сложности. Наибольшую сложность при анализепредставляют проекты класса C – крупные проекты.Для выявления ОРП в сложных проектах ПО разработан метод обнаруженияОРП, который отличается от существующих введением механизма контролясостояний сегментов памяти после построения промежуточного представленияданных в режиме статической отладки.Структурная схема разработанного метода проиллюстрирована на рисунке 2.Метод выявления ошибок при работе с памятью состоит из трех стадий:построения промежуточного представления данных, контроля состояний сегментовдинамически выделенной памяти и генерации сообщений о выявленных ошибках.13На рисунке 3 изображен алгоритм обхода графа вызовов функций.Правила работы семантического анализатора (СА) – это правила выявленияОРП по модели состояний объектов памяти.Будем обозначать объект динамически выделенной памяти M i j , где i порядковый номер вызова функции работы с динамической памятью в функции всоответствии с таблицей сведений по функциям работы с памятью, j - порядковыйномер функции в таблице описаний функций.Рисунок 2.

Структурная схема метода выявления ошибок14mainРегистрация  вызова  функцииПереход  к  следующей  функции  в  графе  по  горизонталиПереход  к  следующей  функции  в  графе  по  вертикали  внизСодержит  нерекурсивные  вызовы?даИмеются  параллельные  ветви  справа?данетСемантический  анализ  (СА)нетСА  вызывающей  функции  (переход  вверх  по  графу)даОстались  необойденные    ветви?нетконецРисунок 3. Блок-схема алгоритма обхода графа вызовов функцийОпределим RS - множество допустимых состояний памяти:•«память, выделенная функцией malloc()»;•«память, выделенная оператором new()»;•«ресурс, выделенный функцией fopen()»;•«ресурс, выделенный функцией popen()»;•«память, освобожденная функцией free()»;•«память, освобожденная оператором delete»;•«ресурс, освобожденный функцией fclose()»;•«ресурс, освобожденный функцией pclose()»;•«пустое состояние (не соответствует ни одному из названных выше)».Определим RA - множество допустимых действий над объектом памяти:•выделение памяти функцией malloc() и производными;•выделение памяти оператором new;•выделение ресурса функцией fopen() и производными;•освобождение памяти функцией free();•освобождение памяти оператором delete;•освобождение ресурса функцией fclose() и производными;•выделение памяти функцией asprintf() и производными;•бездействие.Введем условные обозначения для элементов таблицы состояний памяти:15Ψ ( M i j ) - имя переменной, содержащей указатель на сегмент памяти;Ω( M i j ) - текущее состояние объекта памяти; Ω ∈ RS ;Ωк ( M i j ) - конечное состояние памяти; Ωк ∈ RS ;Ω0 ( M i j ) - первоначальное состояние памяти; Ω0 ∈ RS .Обозначим η - номер параметра в функции, которым является данный объектпамяти.

Данный параметр используется при межпроцедурном анализе и задаетсязначением «-1» для идентификации возвращаемого значения оператором return илипорядковым номером параметра в вызывающей функции.В таком случае множество имен указателей на динамически выделеннуюпамять, которые хранятся в таблице состояний памяти, будем обозначать RΨ .Введем условные обозначения для элементов таблицы сведений по функциямработы с памятью:Ψ 0 ( M i j ) - первоначальное имя переменной-указателя на динамическивыделенную память;Ψ k ( M i j ) - новое имя переменной-указателя на динамически выделеннуюпамять.Будем обозначать текущее действие ϕ над объектом памяти M i j - ϕ ( M i j ) .Данное действие соответствует некоторому типу работы с памятью: ϕ ( M i j ) ∈ RT .Модель состояний объектов памяти, строящаяся при внутрипроцедурноманализе каждой функции для объекта памяти, который является локальным дляданной функции, выглядит следующим образом:{ Ψ ( M i j ) = ∅ : [ Ψ ( M i j ) = Ψ 0 ( M i j ) ; Ω0 ( M i j ) = ϕ ( M i j ) ; Ω( M i j ) = Ω0 ( M i j ) ; Ωk ( M i j ) = Ω( M i j ) ]},{ Ψ ( M i j ) ≠ ∅ : [ Defect0 ( Ω( M i j ) , ϕ ( M i j ) ); Ω( M i j ) = ϕ ( M i j ) ; Ωk ( M i j ) = Ω( M i j ) ]}.(1)Defect0 - правила выявления ОРП.Запись Ψ ( M i j ) = ∅ : означает, что далее рассматривается математическоеописание состояния для нового объекта памяти.Модель состояний объектов памяти, строящаяся при межпроцедурноманализе, выглядит следующим образом:{ Ψ 0 ∈ RΨ ,η ≠ ∅ :[ Ψ ( M i j ) = Ψ k ( M i j ) ; Ω( M i j ) = ϕ ( M i j ) ]}(2)Для обозначения соответствия состояния памяти Ω одному из значениймножества состояний памяти будет использоваться следующая запись:Ω∈ RS [a − b] , которая обозначает, что данное состояние совпадает с одним изсостояний: Ra , Ra +1 ,..., Rb −1, Rb , где a < b .Аналогично для имен переменной, являющихся указателем на выделеннуюпамять.Правила выявления ОРП Defect0 , используемые при построении икорректировки таблицы состояний памяти, выглядит следующим образом:Обнаружение ошибки 1 вида ( Err1 ) «Повторное выделение ресурса без егопредварительного освобождения» выполняется с помощью следующего правила:16(3)Err1 : { Ω( M i j ) ∈ RS [1 − 4], Ψ ( M i j ) ∈ RA [1, 2,3, 7]}.Обнаружение ошибки 2 вида ( Err2 ) «Потеря последней ссылки на ресурс»выполняется с помощью следующего правила:(4)Err2 : { Ψ ( M i j ) ∈ RA [1, 2,3, 7], Ψ ( M i j ) = ∅ , N = ∅ }.Обнаружение ошибки 3 вида ( Err3 ) «Освобождение ресурса до его выделения»выполняется с помощью следующего правила:(5)Err3 : { Ω0 ( M i j ) ∈ RS [5 − 8] }.Обнаружение ошибки 4 вида ( Err4 ) «Повторное освобождение ресурса»выполняется с помощью следующего правила:(6)Err4 : { Ω( M i j ) ∈ RS [5 − 8] , Ψ ( M i j ) ∈ RA [4 − 6] }.Обнаружение ошибки 5 ( Err5 ) вида «Освобождение ресурса функцией, непредназначенной для освобождения этого типа ресурсов» выполняется с помощьюследующих правил:Err5 : { Ω( M i j ) ∈ RS [1] , Ψ ( M i j ) ∈ RA [5, 7] };Err5 : { Ω( M i j ) ∈ RS [2] , Ψ ( M i j ) ∈ RA [4, 6] };(7)Err5 : { Ω( M i j ) ∈ RS [3, 4] , Ψ ( M i j ) ∈ RA [4,5] }.Для окончательного выявления ОРП на этапе выявления ошибок помимоалгоритма Defect0 используется следующее правило:(8)Err2 : { Ωк ( M i j ) ∈ RS [1 − 4] },Разработанный метод статического выявления ошибок при работе с памятьюпозволяет обнаруживать ОРП за короткое время в крупных проектах.Также в данном разделе приводится оценка сложности разработанногоалгоритма, которая выражается формулой:(9)O(R+L)*N2,гдеR - глубина графа вызовов.L – размер функции в строках.N - количество определенных в проекте функций.В третьем разделе рассмотрены практические аспекты реализациирезультатов исследования.Memory-related Errors Detection and Isolation System (MEDIS) – программноинструментальное средство обнаружения и локализации ошибок, связанных сраспределением сегментов оперативной памяти принцип работы которого основанна разработанном методе выявления ошибок в ПО.Для оценки эффективности работы программно-инструментальных средств(ПИС) выявления ОРП предлагается следующий набор показателей качества (ПК),характеризующих работу:•состав ошибок (виды ОРП), выявляемых данным ПИС,•число выявленных (или, наоборот, число не выявленных) ошибок,•число выявленных ошибочно (ложных) ошибок,17•время работы (необходимое время для выполнения всехпредусмотренных операций).Для сравнения выбрано ПИС Cppcheck в связи с тем, что данное средствошироко распространено и имеет открытый исходный код.Оценка ПК ПИС MEDIS и Сppcheck проводилась по результатам их работы напроектах ПО всех трёх классов.