Common Intermediate Language и системное программирование в Microsoft.Net. Макаров А.В - 82 стр.

UptoLike

ВУЗ: 

МГТУ им. Баумана | Москва

Составители: 

Рубрика: 

4.3.3.3. Описание алгоритма
В процессе работы алгоритма для каждой инструкции CIL вычисля-
ется конфигурация стека. При этом фактические значения, лежащие на
стеке, в локальных переменных и параметрах метода, не учитываются.
Алгоритм верификации работает со следующими данными:
• Неизменяемые данные:
o Метаданные сборки, в том числе количество и типы ло-
кальных переменных и параметров метода.
o Массив P, содержащий инструкции CIL в том порядке, в
каком они записаны в теле метода. Пусть N – количество
инструкций.
• Изменяемые данные:
o Массив M размера N, в котором хранятся вычисляемые в
процессе верификации конфигурации стека.
Возможны два результата работы алгоритма:
• Успешная верификация.
Метод не содержит неверифицируемых инструкций. Все воз-
можные пути передачи управления в теле метода рассмотрены.
Для каждой инструкции вычислена конфигурация стека.
• Неуспешная верификация.
Метод либо содержит неверифицируемые инструкции, либо в
процессе вычисления конфигурации стека для некоторой инст-
рукции было выявлено противоречие.
В начале работы алгоритма в массиве M не записано ни одной конфи-
гурации.
Алгоритм последовательно просматривает массив P, то есть на каж-
дом шаге работает с одной инструкцией P[i], где i пробегает значения от
1 до N (будем считать, что массивы P и M нумеруются, начиная с единицы).
На каждом шаге алгоритма выполняются следующие действия:
1. Итак, P[i] – текущая рассматриваемая инструкция. Тогда смот-
рим, что собой представляет M[i]. Если M[i] еще не содержит
конфигурацию стека, то записываем в M[i] пустую конфигура-
цию.
2. Проверяем, верифицируема ли инструкция P[i], учитывая кон-
фигурацию стека M[i] и информацию, содержащуюся в мета-
данных. Если инструкция в принципе не верифицируема или
не может быть выполнена при заданной конфигурации стека, то
алгоритм завершается неуспехом.
3. Осуществляем абстрактное выполнение инструкции P[i]. Дру-
гими словами, вычисляем конфигурацию стека S, которая полу-
чилась бы после реального выполнения инструкции.
4. Определяем, на какие инструкции может быть передано выпол-
Анализ кода на CIL
151
4.3.3.2. Конфигурации стека
Будем называть конфигурацией стека данные о количестве слотов на
стеке и типы значений, лежащих в этих слотах. При этом конфигурацию,
содержащую 0 слотов, будем называть пустой конфигурацией.
Рассмотрим две операции над конфигурациями, которые использу-
ются в алгоритме верификации:
1. проверка совместимости двух конфигураций;
2. слияние двух конфигураций.
Операция проверки совместимости имеет два операнда: конфигура-
ции C и K. Она возвращает булевское значение, показывающее, совмести-
ма ли конфигурация C с конфигурацией K.
Приведем алгоритм вычисления операции проверки совместимости:
1. Если количество слотов в конфигурациях C и K различно, то воз-
вращаем false. В противном случае пусть N – количество слотов
в конфигурации C (естественно, и в K тоже).
2. Если N = 0, то возвращаем true.
3. Пусть i пробегает значения от 1 до N.Тогда для каждого такого i
выполняем следующее:
a. пусть S – тип i-го слота конфигурации C, а T – тип i-го сло-
та конфигурации K;
b. если не T := S, то возвращаем false.
4. Возвращаем true.
Операция слияния двух конфигураций также имеет два операнда:
конфигурации C и K. Она может либо закончиться неуспехом, либо возвра-
щает конфигурацию R, вычисляемую по следующему алгоритму:
1. Если количество слотов в конфигурациях C и K различно, то ал-
горитм завершается неуспехом. В противном случае пусть N –
количество слотов в конфигурации C (естественно, и в K тоже).
2. Если N = 0, то возвращаем пустую конфигурацию.
3. Пусть i пробегает значения от 1 до N.Тогда для каждого такого i
выполняем следующее:
a. пусть S – тип i-го слота конфигурации C, а T – тип i-го сло-
та конфигурации K.
b. вычисляем тип Ui-го слота результирующей конфигура-
ции:
i. если S := T, то U = S.
ii. в противном случае, если T := S, то U = T.
iii.в противном случае, если T и S – объектные типы и у
них существует ближайший базовый тип V, то U = V.
iv. в противном случае, алгоритм завершается неуспехом.
4. Возвращаем результирующую конфигурацию.
150
CIL и системное программирование в Microsoft .NET
150                           CIL и системное программирование в Microsoft .NET   Анализ кода на CIL                                                   151


4.3.3.2. Конфигурации стека                                                       4.3.3.3. Описание алгоритма
     Будем называть конфигурацией стека данные о количестве слотов на                   В процессе работы алгоритма для каждой инструкции CIL вычисля-
стеке и типы значений, лежащих в этих слотах. При этом конфигурацию,              ется конфигурация стека. При этом фактические значения, лежащие на
содержащую 0 слотов, будем называть пустой конфигурацией.                         стеке, в локальных переменных и параметрах метода, не учитываются.
     Рассмотрим две операции над конфигурациями, которые использу-                      Алгоритм верификации работает со следующими данными:
ются в алгоритме верификации:                                                              • Неизменяемые данные:
         1. проверка совместимости двух конфигураций;                                           o Метаданные сборки, в том числе количество и типы ло-
         2. слияние двух конфигураций.                                                             кальных переменных и параметров метода.
     Операция проверки совместимости имеет два операнда: конфигура-                             o Массив P, содержащий инструкции CIL в том порядке, в
ции C и K. Она возвращает булевское значение, показывающее, совмести-                              каком они записаны в теле метода. Пусть N – количество
ма ли конфигурация C с конфигурацией K.                                                            инструкций.
     Приведем алгоритм вычисления операции проверки совместимости:                         • Изменяемые данные:
         1. Если количество слотов в конфигурациях C и K различно, то воз-                      o Массив M размера N, в котором хранятся вычисляемые в
            вращаем false. В противном случае пусть N – количество слотов                          процессе верификации конфигурации стека.
            в конфигурации C (естественно, и в K тоже).                                 Возможны два результата работы алгоритма:
         2. Если N = 0, то возвращаем true.                                                • Успешная верификация.
         3. Пусть i пробегает значения от 1 до N. Тогда для каждого такого i                  Метод не содержит неверифицируемых инструкций. Все воз-
            выполняем следующее:                                                              можные пути передачи управления в теле метода рассмотрены.
               a. пусть S – тип i-го слота конфигурации C, а T – тип i-го сло-                Для каждой инструкции вычислена конфигурация стека.
                  та конфигурации K;                                                       • Неуспешная верификация.
               b. если не T := S, то возвращаем false.                                        Метод либо содержит неверифицируемые инструкции, либо в
         4. Возвращаем true.                                                                  процессе вычисления конфигурации стека для некоторой инст-
     Операция слияния двух конфигураций также имеет два операнда:                             рукции было выявлено противоречие.
конфигурации C и K. Она может либо закончиться неуспехом, либо возвра-                  В начале работы алгоритма в массиве M не записано ни одной конфи-
щает конфигурацию R, вычисляемую по следующему алгоритму:                         гурации.
         1. Если количество слотов в конфигурациях C и K различно, то ал-               Алгоритм последовательно просматривает массив P, то есть на каж-
            горитм завершается неуспехом. В противном случае пусть N –            дом шаге работает с одной инструкцией P[i], где i пробегает значения от
            количество слотов в конфигурации C (естественно, и в K тоже).         1 до N (будем считать, что массивы P и M нумеруются, начиная с единицы).
         2. Если N = 0, то возвращаем пустую конфигурацию.                              На каждом шаге алгоритма выполняются следующие действия:
         3. Пусть i пробегает значения от 1 до N. Тогда для каждого такого i               1. Итак, P[i] – текущая рассматриваемая инструкция. Тогда смот-
            выполняем следующее:                                                              рим, что собой представляет M[i]. Если M[i] еще не содержит
               a. пусть S – тип i-го слота конфигурации C, а T – тип i-го сло-                конфигурацию стека, то записываем в M[i] пустую конфигура-
                  та конфигурации K.                                                          цию.
               b. вычисляем тип U i-го слота результирующей конфигура-                     2. Проверяем, верифицируема ли инструкция P[i], учитывая кон-
                  ции:                                                                        фигурацию стека M[i] и информацию, содержащуюся в мета-
                     i. если S := T, то U = S.                                                данных. Если инструкция в принципе не верифицируема или
                     ii. в противном случае, если T := S, то U = T.                           не может быть выполнена при заданной конфигурации стека, то
                     iii.в противном случае, если T и S – объектные типы и у                  алгоритм завершается неуспехом.
                         них существует ближайший базовый тип V, то U = V.                 3. Осуществляем абстрактное выполнение инструкции P[i]. Дру-
                     iv. в противном случае, алгоритм завершается неуспехом.                  гими словами, вычисляем конфигурацию стека S, которая полу-
         4. Возвращаем результирующую конфигурацию.                                           чилась бы после реального выполнения инструкции.
                                                                                           4. Определяем, на какие инструкции может быть передано выпол-

Страницы