STATISTIC METHOD OF SUMMARY COMPLEXITY MEASURES CRITERIA BUILDINGOF THE ON-BOARD SOFTWARE FOR THE COMMUNICATION AND NAVIGATION SATELLITES

Аннотация

Analyzed statistic data of the program complexity measures for the on-board control software. Realized statistic dis- tribution functions for complexity measures of the on-board program MODULA-2 and defined coefficients for Poison functions. It is proposed the method to build summary complexity measures and criteria definitions for the summary measures on the base of statistic data.

Толық мәтін

Повышение надежности бортового программного обеспечения (БПО) спутников связи и навигации яв- ляется актуальной задачей. Под надежностью про- граммного обеспечения понимается отсутствие оши- бок в бортовых программах, выявляемых в летной эксплуатации. На общее повышение надежности бор- тового программного обеспечения направлена техно- логия разработки и верификации бортового про- граммного обеспечения [1; 2], разработанная и вне- дренная на ФГУП «Научно-производственное объе- динение прикладной механики имени академика М. Ф. Решетнева». Средства измерения бортового программного обеспечения [3] являются частью этой технологии. Количество ошибок, не обнаруженных при верификации и тестировании БПО, зависит от сложности бортовых программ. Одной из задач средств измерения является получение мер сложности исходного текста бортовых программ и проверка их на критерии. Бортовое программное обеспечение разрабатыва- ется в кросс-системе программирования на языке МОДУЛА-2. В работе [4] определены наборы мер сложности для программ на языке МОДУЛА-2. В Ин- ституте систем информатики СО РАН (Новосибирск) и ООО «Эксельсиор» разработан метрический компи- лятор, внедренный в НПО ПМ в составе средств изме- рения кросс-системы программирования. Некоторые критерии простых мер сложности в средствах измерения были установлены по эксперт- ным оценкам. Экспертная оценка оказалась не очень хорошим способом определения границ критериев и часто вызывает непонимание и возражения со сторо- ны программистов. Например, нельзя устанавливать Большая величина меры 1-й категории означает по- вышенную сложность кода и соответствует большему числу ошибок в программе. Меры 2-ой категории не связаны со сложностью кода, но отражают разный уро- вень понимания текста программы, что также оказыва- ет влияние на количество ошибок в программе. Рассмотрим наиболее разнообразный по видам мер сложности набор мер процедур, вычисляемый метри- ческим компилятором. Список мер сложности проце- дур приведен в первом столбце таблицы. С помощью средств измерения [3] и базы данных управления работами СОКРАТ-УР [5], дополнительно хранящей данные о мерах, были собраны данные по мерам сложности программ бортового комплекса управления на выборке, включающей 233 процедуры. Данные по мерам процедур обработаны в Microsoft Excel, аппроксимированы функциями распределения вероятности, построены диаграммы. Большая часть мер имеет функцию распределения вероятности Пуассона. Только для трех мер из 27 наблюдается другое распределение вероятности: М16, М22 и М27. Очевидно, что для мер, выраженных в процентах, функция Пуассона не подходит, а мера М16 зависит от средней длины слова в обычном языке. Меры, не подчиняющиеся функции распределения Пуассона, относятся ко второй категории мер. Обработка данных выборки процедур выявила, что вероятность меры Mik, где i - номер меры; k - номер процедуры, аппроксимируется функцией распределе- ния Пуассона с коэффициентом K1: (li ) x жесткую границу длины процедуры, не учитывая ее топологическую сложность, количество переменных, image , e P l(x) = -l x! i (1) объем внешнего интерфейса. Появляется необходи- мость собрать и изучить реальные данные по стати- стике мер, определить комплексные меры сложности и установить критерии по комплексным мерам. Метрический компилятор языка МОДУЛА-2 вы- числяет 27 мер процедур, 22 меры тела модуля и 21 меру модулей. Все меры можно разделить на две кате- гории: меры, связанные со сложностью кода програм- мы на языке программирования; меры, повышающие способность программиста понимать сложный код программы. Меры объема, топологические меры и меры ин- терфейса относятся к мерам 1-й категории. К мерам 2-ой категории относятся меры комментируемости и именования объектов. где x = Int(Mik/K1i) = 0, 1, … - целое число; li - параметр Пуассона для i-ой меры. Для функции вероятности Пуассона математиче- ское ожидание и дисперсия i-ой меры будет: M(Mik ) = D(Mik ) ~ li K1i . (2) Коэффициент K1i является шириной единичного интервала, в который попадает значение i-й меры, так чтобы частота попадания значения меры в единичные интервалы могла бы быть успешно аппроксимирована дифференциальной функцией распределения вероят- ности Пуассона (1) с некоторым li. Целочисленный коэффициент K1i легко определялся в Microsoft Excel, а параметр li уточнялся методом наименьших квадра- тов. Параметры K1i и li, полученные по результатам обработки выборки процедур, приведены в таблице. Параметры аппроксимирующих функций Пуассона для мер сложности процедур Наименование меры K1i li M(Mik) K2i M1. Общее число вызовов 1 2,40 2,4 21 M2. Число различных вызовов 1 2,70 2,7 21 M3. Число локальных объектов 2 1,10 2,2 7 M4. Число параметров 2 0,5 1 7 M5. Число операторов 7 1,15 8,05 - M6. Число операторов управления 3 1,44 4,32 21 M7. Число циклов 1 0,4 0,4 7 M8. Число операторов с присваиванием 4 1 4 21 M9. Число не пустых строк 7 3,8 26,6 7 M10. Число комментариев без учета влож. процедур 7 1,72 12,04 7 M11. Число использований глобалов 2 0,7 1,4 7 M12. Число использований импортированных объектов 4 1,25 5 7 M13. Число использований внешних объектов 4 1,75 7 7 M14. Число различных используемых объектов 7 1,9 13,3 7 M15. Число использований объектов 21 1 21 7 M16. Средняя длина имени объекта - - - - M17. Мера Мак-Кейба без учета сложности условия 2 1 2 42 M18. Мера Мак-Кейба с учетом сложности условия 4 0,565 2,26 21 M19. Макс. вложенность структурных операторов 1 1,77 1,77 21 M20. Макс. вложенность циклов 1 0,4 0,4 7 M21. Число строк комментариев с учетом влож. проц. 7 2,18 15,26 7 М23. Число локальных процедур 1-го уровня 1 0,055 0,055 7 М22. Комментируемость строк = (Число строк комментариев/Число не пустых строк) 100 % - - - - М24. Общее число локальных процедур 1 0,055 0,055 7 М25. Число строк тела 7 2,18 15,26 21 M26. Макс. вложенность IF и CASE операторов 1 1,57 1,5 7 M27. Комментируемость операторов = (Число комментариев/Число операторов) 100 % - - - - Функции вероятности некоторых мер, полученные по данным выборки (ряд 1) и ступенчатые функции Пуассона с коэффициентами K1i и li (ряд 2) показаны на рис. 1-3. Определено, что коэффициент K1i для ряда мер равен 7. Человек способен одновременно удержи- вать в кратковременной памяти не более 7 объектов. К мерам с K1i = 7 относятся меры длины (число строк тела процедуры, число операторов), меры объема словаря (число различных используемых объектов), и производные от них меры: число строк всех комментариев, число непустых строк. Так как все различные используемые объекты делятся на локальные и глобальные, включают импортирован- ные объекты, то коэффициенты K1i для мер импор- тированных, внешних, глобальных, локальных объ- ектов меньше 7. image Рис. 1. Аппроксимация меры М7 (ряд 1) функцией Пуассона с К17 = 1 и l7 = 0,4 (ряд 2) image Рис. 2. Аппроксимация меры М9 (ряд 1) функцией Пуассона с К19 = 7 и l9 = 3,8 (ряд 2) image Рис. 3. Аппроксимация меры М19 (ряд 1) функцией Пуассона с К119 = 1 и l19 = 1,77 (ряд 2) Хорошо видно, что сумма коэффициентов K16 = 3 для меры числа операторов управления и K18 = 4 для меры числа операторов присваивания равна коэффи- циенту K15 = 7 для меры числа всех операторов. Для меры числа параметров процедуры коэффициент K1 равен двум, это связано с парами вход-выход для параметров процедуры. Меры Мак-Кейба имеют тоже коэффициенты, кратные двум: K117 = 2 и K118 = 4, это можно объяснить делением программы в основ- ном на две логические ветки в узловых точках графа программы. Можно предположить, что коэффициенты К1i не должны зависеть от выборки процедур. От выборок процедур, написанных разными группами, програм- мистами разной квалификации и в разных условиях, должны зависеть параметры Пуассона li. Для построения комплексных мер сложности и определения их критериев будем использовать меры процедур 1-й категории, распределенные по функции Пуассона. Критерии мер 2-й категории (комменти- руемость, именование) определяются методом экс- пертных оценок: для улучшения чтения и понимания текста программы. Комплексную меру процедуры (КМП) определим в виде точки в пространстве из m измерений, компонен- тами которого является набор нескольких мер из табравна функции Пуассона от любой из координат Pl(xi). Формулу (4) можно записать в виде ¥ W лицы с учетом коэффициентов K1i: КМП = (Mi1k/K1i1, Mi2k/K1i2,… Mimk/K1im), где m - размерность простран- F КМП = ò s =RW fКМП (S)dS < e, (7) ства выбранных мер. Для взаимно независимых мер вероятность комплексной меры определяется произ- ведением вероятностей функций распределения (1): m где S - длина вектора КМП = (x1, x2, … xm) из нулевой точки, интегрирование ведется вдоль линии биссектрисы. Написана компьютерная программа, вычисляющая fКМП = ÕPli (xi ). (3) вероятность FΩ КМП попадания в хвост функции расi =1 Интегральная функция вероятности комплексной меры FКМП есть сумма дискретных вероятностей (3) по всему пространству мер из m-измерений. При сумми- ровании по всему пространству мер FКМП = 1. Перехо- дим от суммирования к интегрированию и определим границу критерия комплексной меры в виде поверх- ности Ω с размерностью m - 1 такой, что интеграл в пределах от Ω до бесконечности меньше e: пределения комплексной меры по формулам (4) и (7) для заданных параметров R, l, m. Параметр R = xi за- давался в виде целых положительных чисел вдоль оси мер. Для независимых мер интегрирование выполня- лось по сфере радиуса R = xi, откуда RΩ оценивается по R. Для зависимых мер радиус сферы RΩ оценивает- ся по его проекции R = xi и уточняется при заданном параметре e с применением аппроксимирующей функции вида W F КМП = ¥ ... m Õ Pl (xi )dx1...dxm < e. (4) ( ) x òò ò i l = i -l (8) W i =1 P l (x) e , Будем искать границу Ω в виде сферической по- верхности, применяя ряд упрощений. Не обязательно строить КМП на полном наборе мер. Построим КМП на независимых мерах, имеющих распределение Пу- ассона с близкими значениями параметра li ~ l. Диф- ференциальная функция распределения fКМП, формула (3), будет иметь наибольший максимум в точке с ко- ординатами (l1, l2, … lm). Функция fКМП будет иметь форму неправильного колокола. Вдоль линии, равно- удаленной от осей пространства мер, функция fКМП имеет минимум и выражается формулой m Г (x + 1) i где Г(x+1) - гамма-функция; x - положительное дей- ствительное число. По результатам вычислений можно составить таб- лицы для выбора радиуса границы критерия RΩ по заданным l, m и при желаемом значении e. Получено, что при одинаковых e граница RΩ для независимых мер меньше границы RΩ для зависимых мер. Средствами Microsoft Excel посчитана корреляционная матрица для мер, приведенных в таблице, на рассматриваемой выборке 233 процедуры. Большая часть мер имеют высокие положительные коэффициfКМП = Pl (x) . (5) енты корреляции порядка 0,6…0,9 и выше. Низкие Максимумы fКМП будут находиться вдоль прямых, расположенных на расстоянии l параллельно к осям m-пространства. Функция fКМП вдоль прямых прини- мает значения коэффициенты корреляции имеют следующие меры: число параметров процедуры, средняя длина имени и меры комментируемости. Так как большая часть мер имеют высокие коэффициенты корреляции, целесообfКМП = Pl (l) m-1 Pl (x). (6) разно выбирать границу RΩ для зависимых мер. e выбирается по экспертной оценке: Однако, оценивая границу критерия КМП, нельзя не учитывать взаимную зависимость мер, и формула Значение предположим, что 1 % всех процедур являются самыми сложными, тогда e » 0,01. Пользуясь результатами (3) fКМП как произведение функций распределения вероятностей для независимых мер не применима. расчетов, выбираем границу критерия RΩ для e » 0,01. Построенные на взаимно зависимых мерах точки Считаем комплексную меру сложности в виде 1 2 КМП будут группироваться внутри небольшого угла в m-пространстве. Близкий к единице коэффициент корреляции мер с одинаковым l означает расположение точек КМП вблизи линии, равноудаленной от длины вектора КМП = (Mi k/K1i1, Mi k/K1i2,… Mimk/K1im), и сравниваем ее с границей критерия RΩ. Процедурами повышенной сложности будут являться процедуры, удовлетворяющие неравенству m осей пространства мер, будем называть эту линию å(Mi j image K1 )2 > R2 . (9) «биссектрисой». Для взаимно зависимых мер имеет j =1 k i j W место другая форма колокола с тем же наибольшим максимумом в точке (l1, l2, … lm) и с максимумами fКМП вдоль биссектрисы. В предельном случае с коэффициентами корреляции равными единице все точки Причина повышенной сложности процедуры уточняется путем поиска простой меры в компонентах вектора КМП, имеющей максимальное отклонение от ее математического ожидания в единицах дисперсии li: КМП располагаются на биссектрисе, а компоненты ( j æ 1 max Mi imageK1 -l )ö. (10) КМП одновременно принимают одинаковые значения ç è li i j i ÷ ø Функция fКМП приводится к одномерному распреде- лению вдоль биссектрисы, ее значения легко получить по функции Пуассона, с учетом длины вектора КМП. Вероятность fКМП в точке (x1, x2, … xm), x1 = x2 = …= xm Можно отсортировать компоненты вектора КМП в порядке убывания по относительному отклонению, чтобы получить больше информации о мерах с откло- нениями. Построим комплексные меры сложности процедур путем сортировки таблицы по li и выделением не- скольких групп мер с близкими значениями li: КМП1, меры М4(l4 = 0,5), М7(l7 = 0,4), М11(l11 = 0,7), М18(l18 = 0,565), М20(l20 = 0,4); КМП2, меры М3(l3 = 1,1), М5(l5 = 1,15), М8(l8 = 1), М12(l12 = 1,25), М15(l15 = 1), М17(l17 = 1); КМП3, меры М6(l6 = 1,44), М13(l13 = 1,75), М14(l14 = 1,9), М19(l19 = 1,77), М26(l26 = 1,57). Граница RΩ рассчитана и выбрана для зависимых мер при e » 0,01 и составляет RΩ = 4,65 для КМП1, RΩ = 7,93 для КМП2 и RΩ = 9,75 для КМП3. В программе проверки мер на критерии средств измерения бортового программного обеспечения [3] введена проверка на критерии комплексных мер КМП1, КМП2, КМП3 с применением формул (9) и в виде экспериментальной апробации новой ме- тодики. Не все меры процедур вошли в состав компонент КМП, и наборы компонент КМП построены на близ- ких значениях li, а не на основе экспертного выбора мер. Представляет интерес построить КМП независи- мо от величины li из мер разных видов: длины, топо- логии, числа объектов. Для улучшения теоретических оценок хорошо бы- ло бы определить взаимно независимые меры. Высо- кие коэффициенты корреляции мер разных видов обу- словлены зависимостью почти всех мер от числа опе- раторов в процедуре. Разделим значения мер на число операторов в процедуре, назовем полученные меры нормированными мерами. Пересчитаем матрицу ко- эффициентов корреляции для нормированных мер, получается значительное снижение коэффициентов корреляции. Корреляция между нормированными ме- рами числа строк тела, мерой Мак-Кейба, мерой числа используемых объектов и мерой числа операторов низка и составляет около -0,2…0,2, вместо 0,6…0,97 для ненормированных мер. Распределения нормированных мер можно также аппроксимировать функциями Пуассона (1), но для этого требуется введение еще одного коэффициента К2i: ничной поверхности Ω для КМП с компонентами не- зависимых мер, имеющими разные значения li. Веро- ятность комплексной меры будет определяться по формуле (3). Границу Ω нужно искать в виде поверх- ности, удовлетворяющей уравнению fКМП = const. Ус- ловие проверки на критерий (9) превращается в задачу определения, находится ли точка КМП внутри грани- цы Ω. Эти задачи решаемы численными методами. В общем случае, статистический метод определе- ния комплексных критериев мер заключается в сле- дующем: определении статистических функций распреде- ления мер; выборе набора мер для построения комплексной меры. Для упрощения задачи рекомендуется выбирать меры с близкими функциями распределения; построении функции плотности распределения вероятности в пространстве выбранных мер. Необхо- димо учитывать взаимную зависимость мер; построении границы комплексной меры в виде поверхности в пространстве мер. Проверка комплексной меры на критерии имеет два аспекта: определение положения точки комплексной ме- ры относительно граничной поверхности; при выходе комплексной меры за границу крите- рия нужно определить, какие простые меры, являю- щиеся компонентами комплексной меры, оказались причиной выхода комплексной меры за границу. При- чина определяется по наибольшему относительному отклонению простой меры от ее математического ожидания. Исходными данными для построения граничной поверхности является величина вероятности выхода меры за границу критерия, т. е. величина e формул (4), (7). Выбор e может быть сделан по экспертной оценке, или может быть выполнена работа по уточнению e, исходя из требований надежности программного обеспечения. Для выбора e по требованиям надежно- сти необходимо получить статистику ошибок и сопос- тавить ее со статистикой мер сложности в процедурах. По величине комплексной меры сложности можно Ni = image Mik , (11) прогнозировать полное число ошибок в процедуре, и k М 5 K 2 k i где Nik - нормированная мера; M5k - число операторов в процедуре. По смыслу, коэффициент К2i является единичной длиной процедуры, измеряемой в операторах, так что нормированная мера Nik выражает качественную ха- рактеристику процедуры на единицу длины. Напри- мер, нормированная мера Мак-Кейба будет являться мерой не всего графа процедуры, а усредненной ме- рой для единичного фрагмента графа длиной К2i опе- раторов. Коэффициент К2i не влияет на коэффициен- ты корреляции между мерами, но позволяет найти решение в виде других аппроксимирующих функций Пуассона для нормированной меры Nik. Коэффициен- ты К2i приведены в таблице. Получив функции распределения нормированных мер, можно рассматривать задачу определения гра- оценивать вероятность остаточных ошибок, которые могут не обнаружиться на этапах тестирования, и пе- рейдут в эксплуатацию. Почти все ошибки обнаружи- ваются на этапе автономной отладки и тестирования и в базах данных проблем с бортовыми программами не фиксируются. Статистика ошибок, обнаруживаемых после передачи программы, мала, и имеющихся дан- ных недостаточно. Можно разработать программу, встроенную в кросс-систему программирования БПО, предназначенную для сбора статистики ошибок в процедурах на этапах автономного тестирования, со- брать данные и продолжить работу в этом направле- нии. В результате выполненной работы предложен но- вый статистический метод построения комплексных мер сложности и определения критериев мер, опреде- лены пути дальнейших исследований.