СТАТИСТИЧЕСКИЙ МЕТОД ПОСТРОЕНИЯ КРИТЕРИЕВ КОМПЛЕКСНЫХ МЕР СЛОЖНОСТИ ДЛЯ БОРТОВЫХ ПРОГРАММ СПУТНИКОВ СВЯЗИ И НАВИГАЦИИ

Аннотация

Проанализированы статистические данные по мерам сложности программ бортового комплекса управле- ния. Получены функции распределения мер сложности бортовых программ на языке МОДУЛА-2 и определены коэффициенты для функций Пуассона. Предложен метод построения комплексных мер сложности и опреде- ления критериев для комплексных мер на основе статистических данных.

Полный текст

Повышение надежности бортового программного обеспечения (БПО) спутников связи и навигации яв- ляется актуальной задачей. Под надежностью про- граммного обеспечения понимается отсутствие оши- бок в бортовых программах, выявляемых в летной эксплуатации. На общее повышение надежности бор- тового программного обеспечения направлена техно- логия разработки и верификации бортового про- граммного обеспечения [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 приведены в таблице. Получив функции распределения нормированных мер, можно рассматривать задачу определения гра- оценивать вероятность остаточных ошибок, которые могут не обнаружиться на этапах тестирования, и пе- рейдут в эксплуатацию. Почти все ошибки обнаружи- ваются на этапе автономной отладки и тестирования и в базах данных проблем с бортовыми программами не фиксируются. Статистика ошибок, обнаруживаемых после передачи программы, мала, и имеющихся дан- ных недостаточно. Можно разработать программу, встроенную в кросс-систему программирования БПО, предназначенную для сбора статистики ошибок в процедурах на этапах автономного тестирования, со- брать данные и продолжить работу в этом направле- нии. В результате выполненной работы предложен но- вый статистический метод построения комплексных мер сложности и определения критериев мер, опреде- лены пути дальнейших исследований.