Con en s lis s a ailable a ScienceDi ec
Jou nal o Sys ems A chi ec u e
jou nal homepage: www.else ie .com/loca e/sysa c
Towa d Linux-based sa e y-c i ical sys ems—Execu ion ime a iabili y
analysis o Linux sys em calls
Ma kel Gala aga a,b,∗,Cha les-Alexis Le eb e a,Jon Pe ez-Ce olaza a,Jose A. Pascual b
aIke lan Technology Resea ch Cen e, Basque Resea ch and Technology Alliance (BRTA), A asa e/Mond agon, Spain
bFacul y o In o ma ics, Uni e si y o he Basque Coun y (UPV/EHU), Donos ia-San Sebas ián, Spain
ARTICLE INFO
Keywo ds:
Linux
Execu ion ime
Sys em calls
Real- ime
Sa e y-c i ical sys ems
ABSTRACT
Mode n anspo a ion and indus ial domain sa e y-c i ical applica ions, such as au onomous ehicles and
collabo a i e obo s, exhibi a combina ion o escala ing so wa e complexi y and he need o in eg a e
di e se so wa e s acks and machine lea ning algo i hms, consequen ly demanding complex high-pe o mance
ha dwa e. Linux’s ex ensi e pla o m suppo and lib a y ecosys em make i a aluable gene al-pu pose
ope a ing sys em o de eloping complex so wa e sys ems. Howe e , because he Linux ke nel has no been
designed o comply wi h sa e y s anda ds, i has a high execu ion pa h a iabili y and does no p o ide
execu ion ime gua an ees. In his con ex , se e al esea ch ini ia i es ha e s udied he usage o Linux o
de eloping complex sa e y- ela ed sys ems, ocusing on opics ha include i s de elopmen p ocess, isola ion
a chi ec u es, o es co e age es ima ion. None heless, execu ion- ime analysis and p o iding empo al
gua an ees is s ill a challenge. This wo k ex ends he no el s a is ical analysis o Linux sys em call execu ion
pa hs wi h he analysis o execu ion- ime a iabili y and p oposes a me hod o es ima ing he wo s -case
execu ion ime, o ming a sound app oach o an in-dep h analysis o he Linux ke nel execu ion pa hs and
execu ion imes o sa e y- ela ed sys ems. The p oposed me hod is applied o a ep esen a i e use case ha
implemen s an Au onomous Eme gency B ake applica ion in an NVIDIA Je son Nano boa d connec ed o he
CARLA au onomous d i ing simula o .
1. In oduc ion
Sa e y-c i ical embedded sys ems a e sys ems whose ailu e can lead
o ca as ophic consequences (e.g., human casual ies in au onomous
ca acciden s). They a e p og ammable sys ems composed o elec-
onics and so wa e, and hey need o be de eloped by adhe ing o
s ic sa e y ce i ica ion s anda ds. Examples o such s anda ds a e
he gene ic IEC 61508 o he au omo i e ISO 26262. In he pas ew
decades, di e se indus y sec o s ha e in es ed subs an ially in no el
sa e y-o ien ed sys ems ha ha e he po en ial o b ing abou e olu-
iona y changes ac oss mul iple ma ke domains, pa icula ly wi hin
he ealm o unc ional sa e y. Many o hese pionee ing sa e y- ela ed
sys ems exhibi no able cha ac e is ics, including high pe o mance
equi emen s, escala ing so wa e complexi y, and he inco po a ion
o open-sou ce componen s, along wi h Machine Lea ning (ML) algo-
i hms and associa ed so wa e s acks. Au onomous ca s and au oma ic
ain ope a ion a e some ep esen a i e examples o such sys ems. An
Ope a ing Sys em (OS) can e ec i ely accommoda e he in eg a ion
o hese complex applica ions wi h he equi ed so wa e s acks while
∗Co esponding au ho a : Ike lan Technology Resea ch Cen e, Basque Resea ch and Technology Alliance (BRTA), A asa e/Mond agon, Spain.
E-mail add esses: [email p o ec ed] (M. Gala aga), [email p o ec ed] (C.-A. Le eb e), [email p o ec ed] (J. Pe ez-Ce olaza),
[email p o ec ed] (J.A. Pascual).
simul aneously o e ing comp ehensi e suppo o unc ional sa e y.
As a esul , his could acili a e he usage o complex applica ions in
compliance wi h unc ional sa e y s anda ds [1]. Linux is he leading
OS om embedded sys ems o supe compu e s and almos e e ywhe e
in be ween [2]. In addi ion, Linux has al eady been deployed in c i ical
applica ions (e.g., elecommunica ion, banking) and dependable sys-
ems such as spacec a (e.g., SpaceX Falcon 9, D agon) [3]. The e o e,
he e is g ea in e es in making i s usage in sa e y-c i ical sys ems
possible, since i would g ea ly help educe de elopmen e o s and
cos s. Mul iple wo ks ha e been ca ied ou o join sa e y ce i ica-
ion equi emen s and echnological ad ancemen s, mainly ocusing on
Linux [4–7]. Mo eo e , Linux’s open-sou ce de elopmen model has
been a gued by he SIL2LinuxMP p ojec as possibly alid o IEC 61508
ce i ica ion ia Rou e 3S, also known as ‘‘complian non-complian
de elopmen ’’ [5].
Likewise, he doc o al hesis S a is ical Pa h Co e age o Non-
De e minis ic Complex Sa e y-Rela ed So wa e Tes ing (SPC) [6] p o-
poses s a is ical me hods o o e come he impossibili y o achie ing
h ps://doi.o g/10.1016/j.sysa c.2024.103266
Recei ed 1 Decembe 2023; Recei ed in e ised o m 11 July 2024; Accep ed 24 Augus 2024
Jou nal o Sys ems A chi ec u e 156 (2024) 103266
A ailable online 28 Augus 2024
1383-7621/© 2024 The Au ho (s). Published by Else ie B.V. This is an open access a icle unde he CC BY license ( h p://c ea i ecommons.o g/licenses/by/4.0/ ).
M. Gala aga e al.
100% es co e age o Linux sys em call execu ion pa hs. Tha wo k
ocuses on he es co e age o e e y possible execu ion pa h ha
he Linux sys em calls can ake. The execu ion pa h aken depends
on he s a e o he sys em a ha poin in ime. This s a e depends
on mul iple and complex elemen s o he sys em and canno be con-
olled o p edic ed [6]. The e o e, ob aining a 100% es co e age o
sys em call execu ion pa hs is un easible. Consequen ly, SPC ocuses
on ex ac ing sys em call execu ion pa hs ( aces) in a es ing p ocess,
and s a is ically es ima ing he es co e age and he isk o un es ed
pa hs appea ing when in ope a ion. Howe e , SPC ob ia es execu ion-
ime beha io and solely ocuses on execu ion pa h co e age. Timing
analysis is also essen ial o sa e y-c i ical sys ems, since hey mus mee
ha d eal- ime equi emen s. Fo example, an Au onomous Eme gency
B ake (AEB) mus an icipa e he isk o collision wi hin bounded ime
windows o ac i a e he b akes and slow down he ehicle, a oiding o
minimizing he impac . I he ac i a ion o he b akes is delayed, he
isk o collision is highe . Hence, iming cons ain s a e as c ucial as
unc ional cons ain s.
In his wo k, we ex end SPC by inding a ela ionship be ween
sys em call execu ion pa hs and hei execu ion imes and by explain-
ing how said ela ionship can be used o enhance he execu ion- ime
a iabili y analysis. To do ha , we design a ep esen a i e use case
consis ing o an AEB implemen ed wi h YOLO 3 and un i in an N idia
Je son Nano connec ed o a ehicle in he CARLA simula o . YOLO 3 is
a e y as objec de ec ion model based on a single neu al ne wo k [8].
We also implemen a simple second use case ha does no use he
GPU and TCP/IP communica ion, as he i s does, and jus execu es
a ew sys em calls. This use case allows us o ob ain esul s ha a e
easie o wo k wi h bu help us unde s and he gene al beha io . Bo h
use cases a e explained in mo e de ail in Sec ion 5. In addi ion o
implemen ing he use cases, we ex end he capabili ies o he ools used
in SPC and gi e hem he abili y o ex ac execu ion imes oge he
wi h aces. Nex , we show he link be ween aces and execu ion
imes and explain how i could be exploi ed wi h p obabilis ic me hods.
Finally, we expe imen ally use he men ioned p obabilis ic me hods o
analyze execu ion imes wi h P obabilis ic Wo s Case Execu ion Time
(pWCET), a p obabilis ic me hodology ha can be used o es ima e
wo s -case execu ion imes when s a ic analysis is no possible. To he
bes o ou knowledge, nei he SPC no o he wo k has analyzed Linux
sys em call execu ion ime a iabili y in combina ion wi h sys em call
pa h analysis in he con ex o sa e y-c i ical sys ems.
The goal o ou wo k is o add execu ion imes o he SPC me hod-
ology (which a e dis ega ded by i ), s udy he ela ionship be ween
execu ion pa hs o sys em calls and hei execu ion imes, and p opose
a way o ake ad an age o said ela ionship, o s udy he possibili y o
using Linux in sa e y-c i ical sys ems.
1.1. Con ibu ions
The summa y o he con ibu ions o his wo k is:
•We modi y he ool used by SPC (DB4SIL2) o make i able o
collec execu ion imes oge he wi h sys em call aces and make
he modi ica ions a ailable online.
•We s udy he ela ionship be ween sys em call execu ion pa hs
and hei execu ion ime and ind ha each pa h (unique ace)
has i s own execu ion- ime dis ibu ion.
•We p opose o use pWCET analysis o each unique ace ins ead
o using i wi h all he esul s o he sys em call. This allows us
o ob ain sho e execu ion ime es ima es. We ca y ou a i s
app oach wi h he mos common execu ion pa h o a sys em call.
Howe e , we iden i y some sho comings in ou use o pWCET
ha need o be esol ed in u u e wo k.
•We explain how we in end o u ilize he pWCET es ima es wi h
a un ime moni o ha de ec s i unique aces wi h oo long
execu ing imes a e being execu ed. The moni o elies on he ac
ha each unique ace has i s own execu ion ime dis ibu ion and
no necessa ily on he pWCET es ima es. O he me hods could be
used o model he execu ion ime dis ibu ions o unique aces.
1.2. S uc u e o he pape
The es o his pape is o ganized as ollows: Sec ion 2p esen s
o he wo ks ha ha e also ocused on he usage o Linux in sa e y-
c i ical sys ems, and wo ks ha ha e s udied he Wo s Case Execu ion
Time (WCET) o Linux sys ems. Sec ion 3in oduces wo ks and con-
cep s ha se e as he basis o ou wo k. In Sec ion 4 he me hodology
ollowed in his wo k is explained. Sec ion 5p esen s ou use cases
and he expe imen al se -up. Sec ion 6in oduces he esul s and he
discussion. Finally, Sec ion 7concludes he pape and p esen s some
lines o u u e wo k.
2. Rela ed wo k
Mul iple wo ks ha e s udied he usage o Linux in sa e y-c i ical
sys ems. The doc o al disse a ion S a is ical Pa h Co e age (SPC)
[3,6,9,10] s a is ically analyzes he Linux ke nel execu ion pa hs and
p esen s a me hodology o es ima e he sys em call execu ion pa h
es co e age ob ained in a es ing p ocess and he isk o execu ing
un es ed pa hs. The SIL2LinuxMP p ojec [5] ‘‘aims a he ce i ica ion
o he base componen s o an embedded GNU/Linux RTOS1 unning
on a single-co e o mul i-co e indus ial COTS2compu e boa d.’’ [11].
Va ious wo ks [12–16] se e as p elimina y and as he base o he
SIL2LinuxMP p ojec by analyzing he Linux ke nel’s execu ion pa h
and execu ion ime a iabili y. P e ious o SIL2LinuxMP, he SIL4Linux
p ojec [17] s udied he possibili y o Linux sa is ying SIL 4 in some
es ic i e condi ions, by designing a sys em wi h acing and p o iling
ools, o mal me hods, and a da abase managemen sys em. SIL 4 is he
highes sa e y in eg i y le el in he IEC 61508 s anda d and e e s o
he highes ela i e le el o isk educ ion p o ided by he p o ec ion
laye s on a sa e y-c i ical sys em.
Chen e al. show in hei s udy [18] he di e ences in obse ed
aces in wo di e en scena ios: hey compa e he e ec o di e en
sys em loads in he i s , and hey compa e di e en ile sys ems
in he second. Enabling Linux In Sa e y Applica ions (ELISA) and
Au omo i e G ade Linux (AGL) a e wo o he p ojec s ha aim o
use Linux in sa e y-c i ical en i onmen s. The o me is ocused on
‘‘de ining and main aining a common se o elemen s, p ocesses, and
ools ha can be inco po a ed in o Linux-based, sa e y-c i ical sys ems
amenable o sa e y ce i ica ion.’’ [4]. The la e ’s objec i e is o ‘‘b ing
oge he au omake s, supplie s, and echnology companies o he pu -
pose o building Linux-based, open-sou ce so wa e pla o ms o au-
omo i e applica ions ha can se e as de ac o indus y s anda ds.
AGL add esses all so wa e in he ehicle: in o ainmen , ins umen
clus e , heads-up-display (HUD), elema ics, connec ed ca , ad anced
d i e assis ance sys ems (ADAS), unc ional sa e y, and au onomous
d i ing.’’ [19].
P ocopio e al. [20] claim ha i p ojec s such as SIL2LinuxMP a e
ocused no only on sa e y bu also on secu i y, he in e es o he open-
sou ce communi y o sa e y-c i ical sys ems will inc ease. C a ei o
e al. [21] c ea e a modi ied and minimal Linux ke nel o in eg a e in o
sys ems ha mus comply wi h he ae onau ical ARINC 653 speci ica-
ion. Di e en app oaches ha e also been ollowed [22], in which he
au ho s show a me hodology o ind sou ces o So wa e Aging in he
Linux ke nel, which e e s o he endency o sys ems o show deg ading
pe o mance and e en ually ail due o e o condi ions ha accumu-
la e o e ime, such as ound-o e o s, un eleased memo y egions, o
s o age space agmen a ion. In hei analysis, hey ind ha he Linux
ke nel has bugs ha mani es as a s a is ically signi ican aging end o
memo y consump ion. Finally, Cinque e al. [23] in oduce he concep
o eal- ime con aine s as a solu ion o empo al and aul isola ion in
mixed-c i icali y a chi ec u es. They o e a e e ence a chi ec u e and
1Real-Time Ope a ing Sys em.
2Comme cial-O -The-Shel .
Jou nal o Sys ems A chi ec u e 156 (2024) 103266
2
M. Gala aga e al.
ini ial p o o ype implemen a ion using Docke con aine s o e a Linux
ke nel pa ched wi h PREEMPT_RT. Al hough ou wo k ocuses only on
Linux, he unde lying ha dwa e mus also be app op ia e o sa e y-
c i ical sys ems in a eal use case because ce i ica ion is ob ained o
he en i e sys em, no o i s indi idual componen s. Pe ez-Ce olaza
e al. [7,24] p esen an o e iew o he cu en s a e o a ai s in ha
ega d.
Rega ding wo ks ha ha e s udied he Wo s Case Execu ion Time
(WCET) o Linux sys ems, de Oli ei a e al. [25,26] model he eal-
ime Linux ke nel (pa ched wi h PREEMPT_RT) and de ine a se o
p ope ies and ules ega ding i s iming beha io , o example ule
13 ‘‘(R13): Calling he schedule always esul s in a con ex swi ch’’.
Then, hey execu e an analysis ha ou pu s a heo e ical bound ha
conside s he sou ces o delays, and hey p esen he ool hey de-
eloped o he ask. The esea ch conduc ed by Sil a e al. [27]
p esen s a P obabilis ic Wo s Case Execu ion Time (pWCET) analysis
o a bubble so ing applica ion un in an Ubun u mic ocompu e and
concludes ha Ex eme Value Theo y (EVT) is adequa e o es ima ing
WCETs in complex sys ems. O he wo ks ha e also s udied pWCET in
complex sys ems – hose in which classic s a ic me hods a e un easible
– and a e o e iewed in a su ey by Cazo la e al. [28], concluding
ha p obabilis ic me hods ha e been ex ensi ely in es iga ed in he
su eyed pe iod, mos o hem using EVT.
Wi hin he con ex o using Linux in sa e y- ela ed sys ems, we
p opose o s udy he ime aken by he ke nel’s sys em calls o each
o hei obse ed aces. We plan o associa e he di e en execu ion
pa hs a e sed by ou use cases and hei co esponding execu ion
imes measu ed du ing he obse a ion pe iod. This will be used as he
base o online moni o ing and o check ha , a un ime, he sys em
a e ses he execu ion pa hs ha ha e al eady been seen and whose
wo s -case execu ion imes a e es ima ed be o ehand. O he wise, he
moni o could b ing he sys em o a sa e s a e. This pape ocuses on
a me hodology o associa ing execu ion pa hs and hei co esponding
execu ion imes be o e ope a ional use. As a as we know, he ela ion-
ship be ween Linux sys em calls and ace execu ion imes has no been
s udied in his p ecise con ex . Okech e al. [15] p esen some esul s
showing he ime dis ibu ion o a sys em call, bu do nei he analyze
i no gi e any conclusions in ha ega d. The wo k om Finney [29]
does examine sys em call imings and jus i ies he usage o Linux o
millisecond o de deadlines. Howe e , hey use a single-co e sys em
wi h a 2.2.12 Linux ke nel, and he e o e hei esul s no longe hold
o he complex mul ico e sys ems o oday.
3. P elimina ies
3.1. Te minology
Th oughou his wo k, we adop he e minology used in SPC [6].
We summa ize he e he p incipal e ms.
•Sys em call (o syscall): A unc ion o he Linux ke nel ha se es
as he in e ace be ween ke nel and use space.
•T ace: The execu ion pa h a sys em call ollows, i.e. he speci ic
con ol- low pa h o execu ion i akes. Sys em calls can ollow
di e en execu ion pa hs; hus, mul iple di e en aces can be
gene a ed by he same sys em call.
•Unique ace: A pa icula pa h a sys em call has aken. Fo
example, a sys em call execu ed en imes can gene a e unique
ace Aeigh imes and unique ace B wo imes.
•Mos common ace (MCT): The unique ace ha is mos e-
quen ly a e sed in he execu ion o a sys em call. As explained
in SPC [9], sys em calls end o ollow ce ain pa hs mos o he
ime, while ollowing o he pa hs much less. The o me can be
conside ed he mos common aces o he syscall, while he la e
can be conside ed a e aces.
•Tes campaign: An i e a ion o he es ing p ocess whe e he es ed
applica ion is execu ed a numbe o imes.
3.2. Sa e y-c i ical sys ems and Linux
In b oad e ms, unc ional sa e y is a isk managemen me hodology
applied o elec ical, elec onic, and p og ammable elec onic sys ems.
I s pu pose is o ensu e he in eg i y o p ocesses ha in ol e po en ial
isks o signi ican magni ude ha could lead o acciden s wi h majo
implica ions. In o he wo ds, i aims o p e en unaccep able isks
ha may di ec ly o indi ec ly esul in physical ha m o damage o
people’s heal h. Func ional sa e y can also be de ined as he ‘‘absence
o ca as ophic consequences on he use (s) and he en i onmen ’’ [30].
IEC 61508 [31] is a gene ic unc ional sa e y s anda d used as a
e e ence sa e y s anda d by o he domain-speci ic s anda ds such as
ISO 26262 o au omo i e and EN 50126 o ailways [7,24]. These
s anda ds conside wo basic ypes o e o s: andom ha dwa e e -
o s (e.g., memo y bi - lip) and sys ema ic e o s in oduced in he
de elopmen p ocess (e.g., design e o s).
Linux is a highly complex p oduc , and i s ce i ica ion o sa e y-
c i ical applica ions is no s aigh o wa d. Wo ks ocusing on using
Linux in sa e y-c i ical sys ems do no in end o c ea e a de ini i e
‘‘sa e’’ e sion ha sui s all use cases [5]. Ins ead, he goal is o
demons a e ha , hanks o he Linux de elopmen p ocess and i s
cha ac e is ics, an a gumen can be made o using Linux in sa e y-
c i ical sys ems. Ne e heless, e e y applica ion, ha dwa e se up, and
use case is di e en , and i is up o he de elope s o use Linux in
a sa e and sound way and jus i y he decisions in e ms o sa e y o
make ce i ica ion o hei sys em possible. I is essen ial o emphasize
ha ce i ying a sys em ha uses Linux o unc ional sa e y does no
au oma ically ce i y Linux i sel as a p oduc . Each sys em is unique,
and ce i ica ion is ob ained o he comple e sys em, no indi idually
o i s componen s. Fu he mo e, Linux cons an ly unde goes changes
and canno be conside ed a single inal p oduc bu an e ol ing one.
I is wo h men ioning ha p ojec s ha ocus on he usage o Linux
o sa e y-c i ical sys ems, such as SIL2LinuxMP o ELISA, a e gene ally
no conce ned only wi h he ke nel bu also wi h lib a ies, ools, and
e e y hing ha makes Linux an ope a ing sys em.
3.3. S a is ical pa h co e age
Linux may be ini ially dismissed o sa e y-c i ical applica ions due
o i s di icul - o-p edic na u e caused by i s high execu ion pa h
a iabili y. Howe e , he doc o al hesis i led ‘‘S a is ical Pa h Co -
e age o Non-De e minis ic Complex Sa e y- ela ed So wa e Tes ing’’
(SPC) [6] p oposes a s a is ical app oach as an al e na i e o classic
me hods.
SPC ocuses on Linux sys em call execu ion pa hs. Fi s ly, i ules
ou s a ic analysis as a possibili y. S a ic analysis in ol es analyzing
e e y possible execu ion pa h o a p og am. I is a common app oach in
p og ams ha can ake di e en execu ion pa hs bu in which o cibly
con olling he decision exp ession ha go e ns hem is o e ly di icul .
In o he wo ds, in s a ic analysis, all execu ion pa hs a e analyzed
indi idually, o de e mine i hey a e all sui able o use. Howe e ,
his is no easible o Linux because o he exceedingly la ge numbe
o possibili ies on i s sys em calls, which a e in gene al no ex emely
specialized, bu ins ead do ‘‘one hing’’ unde a la ge numbe o si ua-
ions and ami y in po en ially many execu ion pa hs (as a consequence
o Linux being gene al-pu pose). Mo eo e , indi ec unc ion calls in
he Linux ke nel a e p e alen [9], and s a ic analysis o hese calls
is gene ally conside ed un ac able. Indi ec calls a e unc ion poin e s
ha selec he in oca ion o a speci ic implemen a ion a un ime.
Secondly, as an al e na i e o s a ic analysis, SPC p oposes a dy-
namic analysis o ke nel aces by acing he execu ion pa hs o sys em
calls. This in ol es unning he applica ion epea edly and collec ing
ke nel aces. The wo k uses he concep o unique aces, which
iden i y speci ic execu ion pa hs o sys em calls. Unique aces, he e-
o e, se e o iden i y each possible di e en execu ion pa h ha has
appea ed h oughou he applica ion uns. Wha is obse ed h ough
Jou nal o Sys ems A chi ec u e 156 (2024) 103266
3
M. Gala aga e al.
his analysis is ha , al hough new unique aces con inue o appea
ini ially, he numbe o new unique aces ha appea dec eases as he
numbe o execu ions inc eases. This implies ha , al hough he numbe
o heo e ical possibili ies may be e y la ge, only a ce ain numbe o
possibili ies a e seen in p ac ice. Based on ha in o ma ion, he p ojec
p oposes s a is ical me hods o es ima e he es co e age o possible
unique aces and he isk o sys em calls a e sing an un es ed pa h
a un ime.
3.4. WCET and pWCET
The Wo s Case Execu ion Time (WCET) o a compu e p og am is
he longes amoun o ime i akes o execu e. In eal- ime sys ems, i is
an impo an me ic ha aims o asce ain ha esponse ime h esholds
will no be su passed. The e a e wo main ways o de e mine WCET:
s a ic me hods and measu emen -based me hods [32]. S a ic me hods
seek absolu e heo e ical igo and s ic ly depend on he accu a e
desc ip ion o he iming beha io o he ha dwa e and so wa e in e -
nals. This gene ally p oduces pessimis ic esul s ha a e exace ba ed as
he sys em becomes mo e complex. Measu emen -based me hods, on
he o he hand, execu e he gi en p og am wi h a subse o possible
s a es o alues o all he ea u es ha a ec execu ion imes. I he
p og am we e o be execu ed wi h he alues ha p oduce he wo s -
case execu ion ime, o i all possibili ies we e execu ed, a sa e uppe
bound would be ob ained. Those speci ic alues a e gene ally unknown
and uncon ollable, and execu ing e e y possibili y no mally p o es
un easible. The e o e, only es ima es o dis ibu ions can be ob ained.
The inc easing complexi y o cu en ha dwa e and so wa e makes
bo h ypes o me hods di icul o use, and p obabilis ic easoning aims
o mi iga e hei limi a ions [7,24,28]. P obabilis ic analysis me hods
sample execu ion- ime obse a ions acco ding o gi en c i e ia, and
hen i he esul s o a p obabili y dis ibu ion, hus ob aining he
pWCET es ima ion [28].
P obabilis ic analysis me hods ha e been used wi h Linux sys ems
be o e [27], bu o he bes o ou knowledge, hey ha e ne e been
used ocusing on Linux sys em call aces o s udy he impac ha
execu ion pa h a iabili y has on execu ion imes. In ou wo k, we
use EVT as a ool o es ima e he pWCET o Linux sys em calls. EVT
is used o es ima e he p obabili y o ex eme e en s, which in ou
case a e he WCETs o sys em calls. We also use EVT o assess ha he
size and numbe o campaigns a e s a is ically signi ican , as done in
SPC, by using i wi h he numbe o unique aces ound pe campaign.
Finally, he e is a equi emen o EVT ha da a be independen and
iden ically dis ibu ed (i.i.d.). We es his by using au oco ela ion and
he Kolmogo o –Smi no and Ljung–Box es s.
4. Me hodology
The i s s ep o ou me hod is epea edly execu ing ou p og ams
and eading he ke nel aces hey gene a e. We use wo di e en
use cases. The i s use case, UC1, in ol es a simula ion whe e a
c ash is a oided by using an Au onomous Eme gency B ake (AEB)
implemen ed in he CARLA simula o . The simula ion las s abou 30 s,
and aces o he whole execu ion a e collec ed o analysis. Each un
o he applica ion gene a es a 1.5 GB ace ile. One un o he use
case includes a ound 15000 calls o he SyS_ioc l sys em call. The
second use case, UC2, is a e y simple p og am ha , only execu es he
SyS_opena sys em call wice pe un. Mo e de ails abou bo h use
cases can be ound in Sec ion 5. Due o he di e ence in numbe o
sys em call usage o bo h use cases, UC1 needs ewe uns o yield
s a is ically signi ican esul s, while UC2 needs mo e. Following SPC,
we dis ibu e he execu ion in campaigns. Fo he i s use case (UC1),
we choose o un 10 campaigns o 20 execu ions each. Fo he second
use case (UC2), we execu e 100 campaigns o 1000 uns each. These
choices a e aken based on he alida ion me hodology p oposed by
SPC, i.e., using EVT o de e mine ha he numbe and size o campaigns
a e su icien by es ima ing ha he numbe o unique aces ound pe
campaign would emain s able wi h mo e campaigns.
In his wo k, we ocus on sys em calls because hey a e he in e -
ace o he ke nel and, he e o e, he main way applica ion p og ams
in e ac wi h i . E en hough mo e hings a e happening in he sys em
while ou p og ams a e being execu ed (e.g., ke nel housekeeping), we
choose o ocus on sys em calls only because his app oach allows us
o easily check when and why hey a e execu ed. In addi ion, ocusing
on sys em calls also enables us o use he ools and me hods p e iously
de eloped o SPC. Ex ending he analysis o he en i e ke nel is an
equally challenging and in e es ing con inua ion o his wo k.
Some sys em calls a e execu ed much mo e o en han o he s
o bo h use cases. The e o e, he numbe o execu ions needed o
s udy each sys em call di e s. Fo example, a single un o UC1
includes a ound 15000 SyS_ioc l calls, while a single un o UC2 calls
SyS_ioc l jus once. In addi ion, some sys em calls gene a e mo e
unique aces han o he s o bo h use cases. Fo ha eason, we choose
o ocus on a single sys em call o each use case. Fo UC1, we choose
SyS_ioc l, because i is used by he p og am o communica e wi h
he GPU and execu e he in e ence. The e o e, i may be ega ded as
he mos impo an sys em call o he applica ion, because i is he one
used o de ec he collision. Fo UC2, we choose SyS_opena because i
is he only sys em call ha gene a es s a is ically signi ican esul s o
pos e io analysis due o he simplici y o he use case. The o he sys em
calls used by UC2 only yield one o wo unique aces pe campaign.
Despi e ocusing on hose wo sys em calls, we ha e also seen how he
o he sys em calls show simila esul s, so ou conclusions a e alid o
all o hem despi e needing mo e execu ions o o mally p o e hem.
To collec da a, DB4SIL2 [33] is execu ed in bo h use cases oge he
wi h he p og ams. DB4SIL2 is a ool ha can ead Linux ke nel aces
gene a ed by a p og am un, and ex ac and p ocess in o ma ion. In
he case o he SPC p ojec , i ex ac s he sys em calls he p og am uses
and hei aces, and assigns an MD5 hash o e e y unique ace. The
sligh es di e ence in he ace p oduces a comple ely di e en MD5
hash, so only aces ha a e comple ely iden ical will gene a e he same
hash. This hash is hen used o in es iga e ace equency, iden i y
a e aces, do s a is ical es ima ions, e c. DB4SIL2 uses ace o ob ain
ke nel aces, speci ically he unc ion-g aph ace , which p obes bo h
unc ion en y and exi and ou pu s he ace in a human- eadable
manne , making he ex ac ion o aces and hei analysis easy. In his
wo k, we modi y DB4SIL2 o ob ain he syscall execu ion imes as well.
The DB4SIL2 ool wi h ou modi ica ions can be ound in he ollowing
eposi o y [34].3The unc ion-g aph ace used by DB4SIL2 ou pu s
unc ion execu ion imes, so modi ica ions o ace a e no necessa y.
The e o e, only modi ica ions o DB4SIL2 a e equi ed, allowing i o
ead he execu ion imes om he ace ou pu when a sys em call
end is de ec ed. The MD5 hash is s ill calcula ed wi hou aking he
execu ion ime in o accoun , so we end up wi h he same in o ma ion
as in SPC, bu sa ing execu ion imes oge he wi h aces. The e o e,
we ob ain a collec ion o pai s (hash, execu ion ime) o each
execu ion o he sys em calls, which a e hen g ouped in o campaigns.
Be o e conduc ing any analysis, we assess he s a is ical signi icance
o he da ase using EVT on he (hash) componen o all pai s (hash
, execu ion ime), as done in SPC. No e ha , in his case, we a e
applying he EVT o he numbe o unique aces ound pe campaign,
no o execu ion imes. In SPC, his is done o assess ha he numbe
o campaigns and hei size is su icien ly la ge, and we use i he
same way. Applying he EVT equi es he sub-da ase o mee he
equi emen o being i.i.d.. Fo ha eason, we use au oco ela ion,
Kolmogo o –Smi no , and Ljung–Box es s, basing ou sel es on SPC. In
addi ion, we es he i.i.d. na u e o he sub-da ase (execu ion ime)
because we use EVT o es ima e he pWCET wi h ha sub-da ase , and
he e o e he sub-da ase is equi ed o be i.i.d..
3Ou da a is also a ailable o any in e es ed eade upon eques .
Jou nal o Sys ems A chi ec u e 156 (2024) 103266
4
M. Gala aga e al.
A e assessing he s a is ical signi icance o bo h sub-da ase s
(hash) and (execu ion ime), we ex ac wo me ics: he numbe
o unique aces pe campaign and he equency o hese unique
aces. By compa ing hese alues wi h hose ob ained in he SPC case
s udies [9], we show ha he me hodology is sui able o ou use cases.
The subsequen phase o ou analysis ocuses on explo ing he
ela ionship be ween unique aces and execu ion imes. We examine
he comple e da ase in wo dis inc app oaches o each sys em call:
•Isola ing he sub-da ase (execu ion ime): In his app oach,
we ocus solely on he execu ion imes associa ed wi h a sys em
call, dis ega ding dis inc ions be ween he execu ion pa hs, o
s udy he beha io o he sys em call as a whole and ha e a e -
e ence wi h which we can compa e he execu ion ime beha io
o each unique pa h.
•Conside ing he ull da ase (hash, execu ion ime): He e, we
examine he en i e da ase , analyzing how he unique aces ela e
o execu ion imes.
Then, we explain how we in end o exploi he ela ionship be ween
unique aces and execu ion imes and o e a i s app oach by using
p obabilis ic me hods o es ima e he p obabilis ic WCETs o unique
aces. Fo ha , we i s s udy he execu ion- ime dis ibu ion cu es
o he sys em calls and hei unique aces; nex , we show how hey
exhibi app op ia e beha io o EVT; and, inally, we use EVT o
es ima e pWCETs o he mos common aces. To choose he models
and pa ame e s o he pWCET es ima ions, we base ou sel es on he
li e a u e [27,28], and we es di e en combina ions o pa ame e s,
showing how di e en pa ame e s i di e en da a be e . We choose
o use he Gene alized Ex eme Value (GEV) and Gumbel models,
and we es ima e hei pa ame e s by using he Maximum Likelihood
Es ima ion (MLE) and L-momen s es ima o s. We also es di e en
Block Maxima (BM) sizes, which es ablish he numbe o samples ha
o m each g oup o block, and only he maximum alue o each block
is used o gene a e he model.
Finally, we show how ou app oach o es ima ing he pWCET o
unique aces could be used wi h a un ime moni o in sa e y-c i ical
sys ems. The moni o would examine a un ime ha only es ed
unique aces a e being a e sed and would gi e a wa ning o s op
he sys em i an un es ed pa h is ound. In addi ion, we would know
wi h pWCET which unique aces ha e execu ion- ime es ima es lowe
han equi ed by he cha ac e is ics o he use case. This would allow
us o know ha i any o he unique ace is a e sed, he e is a dange
o su passing he h eshold. Hence, he moni o would also gi e a
wa ning o s op he sys em wi h unique aces ha ha e execu ion- ime
es ima es highe han equi ed. Since aces a e sequences o unc ion
calls, he moni o could compa e e e y s ep o he call chain while
he sys em call is being execu ed, and hence i could know i a dange
exis s be o e he execu ion o he sys em call has inished. We explain
in Sec ion 7 ha his wo k se es as he base o he un ime moni o
and ha we in end o wo k on i in he u u e.
5. Expe imen al se up
The main use case we ha e chosen o ou analysis implemen s an
AEB o he CARLA au onomous d i ing simula o [35]. Speci ically,
we ha e de eloped an applica ion o CARLA in which wo ehicles
a e launched in pe pendicula di ec ions nea an in e sec ion and s a
mo ing owa d i . Bo h ca s each he in e sec ion a he same ime, so
i none o hem b akes, a T-bone c ash happens. To p e en he impac ,
we ha e de eloped an AEB ha s ops one o he ehicles when he
impac is abou o happen. I is composed o a came a in he CARLA
simula o , communica ion be ween CARLA and an embedded pla o m,
and he YOLO objec de ec ion model unning in he embedded pla -
o m. In CARLA, we equip one o he ca s wi h a on al came a ha
con inuously sends ames o an embedded pla o m ha in e s whe he
he e is an obs acle in on . The applica ion unning on he pla o m
Fig. 1. F ame om he came a added o he ca simula ed in CARLA. On he le side
o he image, he o he ca appea s, su ounded by a box ha indica es ha YOLO
iden i ies he objec as a ca .
ecei es ames and passes hem one by one as inpu o he YOLO objec
de ec ion model. YOLO de ec s objec s in an image and ags hem as he
ca ego y o which i belie es hey belong (e.g., ca , ee, a ic ligh ,
e c.). I an obs acle is de ec ed by YOLO, he applica ion execu es a
simple dis ance calcula ion algo i hm o decide i he dis ance o i is
oo sho o he cu en a eling speed o he ehicle, and in ha case,
a b aking o de is sen o he CARLA simula o . When he obs acle is
no longe he e, an accele a ing o de is sen , and he ehicle wi h he
came a s a s mo ing again. The e o e, when he ehicle equipped wi h
he came a de ec s ha he e is ano he ca eaching he in e sec ion,
i b akes and le s i pass. When he in e sec ion is clea , i con inues on
i s way. The i s ame in which he o he ehicle is de ec ed can be
seen in Fig. 1. We call his use case UC1.
UC1 is composed o se e al in e ac ing pa s, such as YOLO, com-
munica ion wi h CARLA, e c., so we ha e analyzed i wi h he s ace
ool and ha e seen ha he SyS_ioc l sys em call is used by YOLO
o communica e wi h he GPU and make he in e ence on each ame
ecei ed om CARLA. Tha is why, as explained in Sec ion 4, we choose
o s udy he SyS_ioc l sys em call.
To be e unde s and ace beha io , we also add a simple use case
ha consis s o an applica ion ha opens /de / andom and /de /
null, eads a by e om he o me , execu es SyS_ioc l, w i es he
by e in he la e , and closes bo h. The applica ion is based on andby e
om [9]. We include he SyS_ioc l sys em call o mimic he beha io
o ou AEB applica ion. This simple applica ion allows us o examine
he ke nel beha io wi hou he added complexi y o he applica ion.
We call his use case UC2.
We execu e he AEB (UC1) in an N idia Je son Nano unning Linux.
The in e ence o de ec he ca in on is done wi h YOLO. CARLA
is execu ed in a Windows PC, and communica ion be ween CARLA
and he AEB happens ia E he ne . The SIL2LinuxMP a chi ec u e is
implemen ed in he Je son Nano o isola e he AEB, allowing i s aces
o be una ec ed by he es o he sys em [5]. The UC2 applica ion is
also execu ed in he N idia Je son Nano, and in his case, he e is no
communica ion wi h he PC. The SIL2LinuxMP isola ion a chi ec u e
is also used. Bo h use cases a e no execu ed a he same ime bu
sepa a ely.
F ace, and speci ically he unc ion-g aph ace , is used o collec
ke nel aces and execu ion imes. We con igu e he ace ac i a ing
he uncg aph-du a ion and g aph- ime op ions. This way, ace
w i es in he ace ile he execu ion ime o a unc ion when i e u ns,
including he execu ion ime o he nes ed unc ions i called. Wi h
hese wo con igu a ions, we ob ain a he e u n o e e y sys em call
he o al ime spen in i . DB4SIL2 uses he ‘‘ ace’’ ile o ead all he
aces a e each un o he use case has inished. Because a un o
UC1 gene a es many aces (a ound 1.3 GB), we con igu e he ile’s
maximum size o be 1.5 GB wi h he bu e _size_kb op ion. In he
Jou nal o Sys ems A chi ec u e 156 (2024) 103266
5
M. Gala aga e al.
Table 1
De ails o he da ase o bo h use cases.
Sys em
call
To al
exec.
To al
unique
aces
App ox. num. o
unique aces
pe campaign
SyS_ioc l
(UC1)
2,902,072 80,118 17,000
SyS_opena
(UC2)
200,000 1,017 104
case o UC2, many ewe aces a e gene a ed, and he de aul bu e
size o a ound 1.5 MB is enough. Enabling ace, and especially he
unc ion-g aph ace , is known o p oduce o e head in he sys em. In
ou case, we a e jus in e es ed in he beha io ac oss mul iple uns
o he same p og am, and since e e y un is a ec ed by he acing
mechanism, we belie e he e ec i has in ou analysis is minimal.
In he Je son Nano, we use Je son Linux R32.7.1 om N idia, which
uses he ke nel e sion 4.9. The only modi ica ion we ha e done o
he ke nel is enabling ace and he unc ion-g aph ace . The CARLA
e sion we use is 0.9.9, wi hou modi ica ions. The i ual came a we
add o one o he ehicles has a esolu ion o 640 ×360 pixels and a
ield o iew o 90◦. Finally, we use YOLO 3 [36] o in e ence.
6. Analysis o he esul s
As explained in he p e ious sec ion, he i s s ep a e collec ing
he da a is assessing i s s a is ical signi icance. Ou da a has he shape
(hash, execu ion ime), and we mus assess he s a is ical signi i-
cance o bo h he hashes and he execu ion imes, he o me o e i y
ha ou da a is simila o ha om SPC and he la e o allow using
EVT wi h i .
Table 1 epo s de ails abou ou da ase . We can see ha bo h
use cases di e g ea ly. Fo example, he analyzed sys em call in UC1
is execu ed many mo e imes han he one analyzed in UC2. This
occu s because one un o he applica ion in UC1 needs o execu e he
sys em call housands o imes, while in UC2 i is execu ed only once.
Mo eo e , ewe unique aces a e gene a ed in UC2, due o he ac
ha he applica ion is less complex.
Fo he sub-da ase (hash), we assess i s s a is ical signi icance by
using EVT, as seen in Table 2. We use he GEV model and he MLE
es ima o . Since da a being i.i.d. is a p econdi ion o EVT, we also show
he esul s o au oco ela ion, Kolmogo o –Smi no , and Ljung–Box
es s. Au oco ela ion is used o check whe he he numbe o unique
pa hs ound in a ce ain campaign has an e ec on he numbe o
unique aces ound in any o he campaign. The Kolmogo o –Smi no
es is used o check i he dis ibu ion o unique aces ound pe
campaign is he same in e e y campaign. The Ljung–Box es is used
o es i campaigns a e independen o each o he by e alua ing any-
o de au oco ela ion. I is simila o au oco ela ion, bu ins ead o
es ing e e y lag sepa a ely, i es s he o e all independence o he
esul s. Wi h au oco ela ion, by eeding i he numbe o unique aces
ound pe campaign, we see ha he numbe o unique aces ound in
a campaign is independen o o he campaigns, as shown in Fig. 2(a).
Fo UC1, we ob ain a maximum co ela ion alue o 0.317, a mini-
mum o −0.329, and a mean alue o −0.056. Ljung–Box also indica es
independence o da a, wi h a 𝑝- alue o 0.895. Finally, we ake wo
andom samples o hal he numbe o campaigns o he Kolmogo o –
Smi no es , and epea i mul iple imes, ob aining p- alues in he
ange [0.3–1]. The p- alues o he wo es s a e a om 0.05, so we
can conclude ha he numbe o unique aces ound pe campaign a e
independen o o he campaigns, and a e iden ically dis ibu ed. The
esul s a e simila o UC2, as seen in Table 2, al hough ha ing di e en
nume ical esul s, hey also ge s able wi h la ge campaign numbe s.
Au oco ela ion is shown in Fig. 2(b), wi h a maximum alue o 0.113,
a minimum o −0.135, and a mean alue o −0.0016. The Ljung–Box es
Fig. 2. Au oco ela ions o he new unique aces ound pe campaign, sub-da ase
(hash).
yields a 𝑝- alue o 0.42, and he Kolmogo o –Smi no es yields alues
in he ange [0.45–1]. In spi e o he good esul s o he Ljung–Box es ,
we can see ha he au oco ela ion esul s a e no op imal. Wo k mus
be done in he u u e o unde s and he cause o i and s eng hen he
assessmen o he s a is ical signi icance o he da a.
Fo he sub-da ase (execu ion ime), we es whe he he da a
is i.i.d., o allow he subsequen es ima ion o pWCETs ia EVT. We
ollow he same p ocedu e as o he (hash) sub-da ase . We show
in Fig. 3 ha au oco ela ion o he execu ion imes o he chosen
sys em calls shows good esul s o bo h o he use cases, bu he Ljung–
Box and Kolmogo o –Smi no es s yield e y small p- alues (<0.05),
he e o e indica ing ha he execu ion imes a e nei he independen
no iden ically dis ibu ed. Wo k mus be done o unde s and why his
happens and whe he i can be sol ed. Fo now, we use he pWCET
me hodology, despi e knowing ou da a is un i o i , wi h he goal
o showing ou app oach, and we lea e he quali a i e analysis o
execu ion imes as u u e wo k.
P oceeding wi h he analysis o he new unique aces ound pe
campaign, we display hem in Fig. 4. As we can see, he beha io
is as expec ed by SPC: e e y subsequen campaign yields ewe and
ewe new unique aces. The igu e shows how UC1 yields many mo e
new unique aces pe campaign han UC2, bu i also shows ha he
end is simila in bo h cases. This also shows why ob aining 100% es
co e age is un easible: e en wi h a high numbe o campaigns, new
unique aces keep appea ing, and he e o e one canno be su e ha
e e y possibili y has been obse ed.
Jou nal o Sys ems A chi ec u e 156 (2024) 103266
6
M. Gala aga e al.
Table 2
Re u n le els es ima ed by i ing unique aces pe campaign da a o he GEV model, using MLE, sub-da ase (hash), and
hei 95% Con idence In e als (CI).
(a) SyS_ioc l sys em call (UC1).
95%
lowe CI
Es ima e
(unique aces)
95%
uppe CI
101-campaign 17,969 18,331 18,694
102-campaign 17,979 18,722 19,466
103-campaign 17,708 18,902 20,097
104-campaign 17,466 18,988 20,509
105-campaign 17,299 19,028 20,758
(b) SyS_opena sys em call (UC2).
95%
lowe CI
Es ima e
(unique aces)
95%
uppe CI
101-campaign 116 120 123
102-campaign 127 134 141
103-campaign 130 143 156
104-campaign 131 149 168
105-campaign 130 154 177
Fig. 3. Au oco ela ions o he sub-da ase (execu ion ime).
Rega ding ace equency, we can see in Table 3 ha he beha io
is also he same in his case: a hand ul o unique aces accoun o a
la ge pe cen age o all execu ions (mos common aces), while o he
unique aces appea e y in equen ly ( a e aces). The e is a big
di e ence be ween use cases in he numbe o mos common aces.
Fig. 4. New unique aces ound pe campaign o execu ions, sub-da ase (hash).
Jou nal o Sys ems A chi ec u e 156 (2024) 103266
7
M. Gala aga e al.
Table 3
Obse ed equency o mos common aces o each sys em call, sub-da ase (hash).
(a) SyS_ioc l sys em call (UC1).
T ace F equency Accumula ed
equency
92b 0.138 0.138
d0e7 0.114 0.252
10a1 0.102 0.354
bb2e 0.074 0.428
b 15 0.058 0.486
a798 0.043 0.529
4027 0.038 0.567
d09 0.035 0.602
ea15 0.021 0.623
439a 0.020 0.644
(b) SyS_opena sys em call (UC2).
T ace F equency Accumula ed
equency
58 6 0.741 0.741
6289 0.200 0.941
685 0.001 0.942
25e7 0.000 0.942
1b99 0.000 0.943
6657 0.000 0.943
d849 0.000 0.943
4164 0.000 0.944
95c 0.000 0.944
921b 0.000 0.944
While he e a e jus wo aces ha accoun o 94% o he execu ions
o SyS_opena in UC2, he 10 mos common aces o UC1 accoun o
64% o he execu ions, he 20 mos common o 75%, and he 944 mos
common o 90%. This is due o applica ion and sys em call complexi y,
while he SyS_opena om UC2 jus opens iles, he SyS_ioc l o
UC1 is used o communica e wi h he GPU and execu e he in e ence,
so a iabili y is a highe .
The beha io shown o new unique aces pe campaign and o he
equency o aces shows how he SPC me hodology is ep oducible
o ou use case. Howe e , going on wi h he es ima ion o he es
co e age and he isk o inding un es ed aces, as done in SPC, is
ou side he scope o his wo k, so we s op in he alida ion phase.
Ins ead, we supplemen he me hodology wi h he analysis o execu ion
imes. Focusing on he en i e (hash, execu ion ime) da ase , we
i s show in Fig. 5 o UC1 and in Fig. 6 o UC2, he di e ence
in he execu ion ime dis ibu ion o he sys em calls as a whole and
all hei unique aces, o de ed om mos o leas common. Sys em
call execu ion imes a e he g ouping o he execu ion imes o all
unique aces. We see how e e y unique ace ollows i s own execu ion
ime dis ibu ion. Some aces co espond o he as es execu ions o
he sys em call, while o he s co espond o he slowes execu ions.
Howe e , an in e es ing end we obse e is ha he mos common
aces ne e seem o be he slowes , and he as es one is among hem.
We can con iden ly say ha he e is a s ong link be ween he execu ion
pa h a e sed in each un o a sys em call and i s execu ion ime.
Since sys em call execu ion imes a e g oupings o di e en iming
dis ibu ions (one o each unique ace), we see in Figs. 7(a) and 7(c)
how his a ec s i s densi y. Ins ead o ha ing a single cu e o bell
om he minimum o he maximum imes, we ind mul iple peaks.
This complica es he pos e io analysis because he beha io is ha d
o model and he e o e p obabilis ic WCET es ima es a e un easible.
Howe e , i we look a he igu es wi h he densi y plo o indi idual
aces, Figs. 7(b) and 7(d), we can see how he seconda y peaks a
om he main peak disappea and all alues a e much close o he
main peak.
The e o e, we can conclude ha analyzing he execu ion imes o
each unique ace independen ly can be bene icial o e s udying sys em
Table 4
Re u n le els es ima ed by he EVT models, (hash, execu ion ime) da ase , and
hei 95% Con idence In e als (CI).
(a) SyS_ioc l sys em call (UC1).
95%
lowe CI
Es ima e
(us)
95%
uppe CI
101- es 589 590 591
102- es 624 627 630
103- es 647 653 658
104- es 663 672 680
105- es 674 686 697
106- es 682 696 710
...
1013- es 696 720 743
1014- es 696 720 745
1015- es 697 721 746
(b) SyS_opena sys em call (UC2).
95%
lowe CI
Es ima e
(us)
95%
uppe CI
101- es 273 274 274
102- es 297 299 300
103- es 321 323 325
104- es 345 348 351
105- es 369 373 376
106- es 393 397 401
...
1013- es 561 570 578
1014- es 585 594 603
1015- es 609 619 629
calls as a whole and dis ega ding dis inc aces, since ha p o es mo e
di icul and yields wo se esul s. Mo eo e , some unique aces show
maximum imes much sho e han he maximum ime o he sys em
call. This is especially ue o he mos common aces. The e o e, hei
pWCET es ima es can be lowe han he es ima es o he sys em call
as a whole. This could be e y use ul i he e was a way o con ol
which unique aces a e execu ed, o a leas o check ha only aces
wi h ‘‘sho ’’ execu ion imes a e being execu ed. We in end o ollow
his wo k by designing a un ime sys em moni o ha checks which
ace is being execu ed, he e o e ensu ing ha i an execu ion pa h
wi h a long execu ion ime we e being aken, he moni o would de ec
i and igge he sys em’s sa e s a e o a oid possibly ca as ophic
consequences. We expand hese ideas in Sec ion 7.
As he i s app oach o hose ideas, we show how he WCET o
unique aces can be es ima ed, by doing i wi h he mos common
aces o bo h applica ions. Fo ha , we use pWCET me hodology. The
i s app oaches o i models o he da a show p omising esul s, as
shown in Table 4. Wi h pa ame e s es ima ed wi h MLE, and o a BM
size o 50, we ob ain obus e u n le el es ima ions, e en o 1015
execu ions. We use he GEV model o UC1, and he Gumbel model
o UC2. I is impo an o emembe ha he i.i.d. hypo hesis ailed
wi h ou da a and ha i is a equi emen o pWCET. Howe e , he
moni o elies on he ac ha each unique ace has i s own execu ion
ime dis ibu ion and no necessa ily on he pWCET es ima es. O he
me hods could be used o model he execu ion ime dis ibu ions o
unique aces (e.g., maximum eco ded alue, maximum accep able
ime, e c.). We lea e he s udy o he causes o he ailu e o he i.i.d.
hypo hesis and he s udy o o he me hods o model execu ion imes as
u u e wo k.
We ha e explo ed di e en models (GEV and Gumbel), di e en
es ima o s (MLE and L-momen s), and di e en BM sizes ( om 10 o
16,000) and conclusions abou he bes i a e unclea . We ha e ound
ha a di e en pa ame e combina ion o each sys em call and unique
ace makes pWCET es ima e alues closes o eali y and p og essi ely
s able as he numbe o es inc eases. Many combina ions gi e a good
i o he model o he da a, bu oo la ge WCET es ima es, and ice
Jou nal o Sys ems A chi ec u e 156 (2024) 103266
8
M. Gala aga e al.
Fig. 5. Execu ion ime dis ibu ions o he SyS_ioc l sys em call and i s mos common aces (UC1), (hash, execu ion ime) da ase . The igu e (b) is iden ical o (a), bu
he e is a limi on he 𝑦-axis.
Fig. 6. Execu ion ime dis ibu ions o he SyS_opena sys em call and i s 20 mos
common aces (UC2), using he (hash, execu ion ime) da ase .
e sa. Wo k mus be done o p ope ly choose he model, es ima o , and
BM size. We also hink ha i would be in e es ing o analyze a Linux
ke nel pa ched wi h PREEMPT_RT and compa e esul s.
Ano he in e es ing esul we see in he igu es is ha he densi y o
he Mos Common T aces (MCTs) o UC1 (Fig. 7(b)) is no comple ely
cen e ed a ound a single alue, despi e all alues being much close o
he main peak han in he densi y o he sys em call (Fig. 7(a)). The
densi y luc ua es a ound di e en execu ion imes. To ule ou ha he
luc ua ions a e caused because o he impac o applica ion complexi y
(UC1 uses compu e ision, GPU, and TCP/IP communica ion), we
show in Fig. 7(d) how UC2 shows he same beha io . These ‘‘jumps’’
make i di icul o i models o he da a, and he e o e complica e
s a is ical analysis.
7. Conclusions and u u e wo k
In his wo k, we in oduce a Linux sys em-call execu ion- ime a i-
abili y analysis ha is based on he SPC me hodology and joins sys em
call aces wi h execu ion imes. To do so, we begin wi h imple-
men ing wo applica ions: UC1, consis ing o an AEB ha uns in an
NVIDIA Je son Nano and is connec ed o he CARLA au onomous d i -
ing simula o ; and UC2, ha jus execu es he SyS_opena ,SyS_ ead,
SyS_ioc l,SyS_w i e, and SyS_close sys em calls. Then, we mod-
i y he ools used in SPC gi ing hem he abili y o ex ac execu ion
imes oge he wi h he aces. Nex , we s udy he ob ained esul s.
Fi s ly, we see ha he numbe o new unique aces ound pe
campaign ollows he beha io expec ed in SPC, o bo h o he use
cases, hus e idencing ha he SPC me hodology can be used in ou
use case.
Secondly, we show ha aces and execu ion imes do ha e a
ela ionship because he execu ion ime dis ibu ion o each unique
ace is also unique and bounded mo e na owly han he execu ion
ime dis ibu ion o he sys em call as a whole. Since each ace has
i s own execu ion- ime dis ibu ion, we could de e mine which aces
a e alid o in alid o he h eshold o ou sys em, depending on
hei execu ion imes. This could be exploi ed i he pa h aken by he
sys em call could be con olled o moni o ed. As explained in SPC, he
con ol o sys em call aces is un easible [9], bu we belie e ha syscall
moni o ing could be used o ensu e ha only alid pa hs a e execu ed.
Thi dly, we explain ha s a ic me hods canno be used o s udy
WCETs o aces, because, as s a ed in SPC, he complexi y o Linux
makes he ask un easible [9]. The e o e, we ca y ou a i s app oach
o using he s a e-o - he-a pWCET analysis wi h unique aces and
show how es ima es o unique aces a e be e han o he sys em call
as a whole. Howe e , we explain how he execu ion ime dis ibu ions
show ‘‘ andom’’ peaks and alleys ha complica e he analysis. In
addi ion, we also explain ha ou da a ails he i.i.d. es , which is
a p e equisi e o he s a is ical ools we use o pWCET analysis, and
he e o e indica es ha ou da a is un i o such ools. S ill, we choose
o ca y ou he pWCET analysis because i allows us o show one way
o exploi he execu ion ime dis ibu ions o unique aces.
Looking o wa d, we in end o epea he analysis in a eal- ime
Linux sys em, pa ched wi h PREEMPT_RT, and compa e he esul s.
We also in end o ocus on he unde lying ha dwa e and s udy i s
impac on ou esul s. We expec o ind how bo h he pa ch and he
ha dwa e a ec ou esul s and o exploi i , aiming o imp o e he
pWCET analysis p esen ed in his pape .
Finally, we also in end o use ou app oach o es ima ing he pWCET
o unique aces o de elop a un ime moni o ha could be used in
Linux-based sa e y-c i ical sys ems. By es ima ing he pWCET o unique
aces, we know which unique aces ha e execu ion imes sho e han
equi ed by he cha ac e is ics o he use case. The moni o will check
a un ime ha he sys em call is a e sing one o hose unique aces,
and no an un es ed one o one ha does no mee equi emen s. I one
o he la e occu s, he moni o will gi e a wa ning o s op he sys em.
This will bene i he sys em in wo ways: (1) he e will be assu ance
ha only es ed unique aces a e being a e sed, and (2) unique aces
ha do no mee equi emen s will be de ec ed be o e he sys em call
inishes. Because unique aces a e chains o unc ion calls, he moni o
will check wi h e e y call i he execu ion pa h is di e ing om he
expec ed, and hence de ec he dange be o e he sys em call has ended.
Jou nal o Sys ems A chi ec u e 156 (2024) 103266
9
