Abstract
Decentralized optimization has found a significant utility in recent years, as a promising technique to overcome the curse of dimensionality when dealing with large-scale inference and decision problems in big data. While these algorithms are resilient to node and link failures, they however, are not inherently Byzantine fault-tolerant towards insider data injection attacks. This paper proposes a decentralized robust subgradient push (RSGP) algorithm for detection and isolation of malicious nodes in the network for optimization non-strongly convex objectives. In the attack considered in this work, the malicious nodes follow the algorithmic protocols, but can alter their local functions arbitrarily. However, we show that in sufficiently structured problems, the method proposed is effective in revealing their presence. The algorithm isolates detected nodes from the regular nodes, thereby mitigating the ill-effects of malicious nodes. We also provide performance measures for the proposed method.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 381-386 |
| Number of pages | 6 |
| Journal | IFAC-PapersOnLine |
| Volume | 52 |
| Issue number | 20 |
| DOIs | |
| State | Published - 2019 |
| Event | 8th IFAC Workshop on Distributed Estimation and Control in Networked Systems, NECSYS 2019 - Chicago, United States Duration: Sep 16 2019 → Sep 17 2019 |
Keywords
- adversarial optimization
- byzantine fault-tolerance
- decentralized optimization
- gradient-based metric
- multi-agent systems
ASJC Scopus subject areas
- Control and Systems Engineering
Fingerprint
Dive into the research topics of 'Detection and Isolation of Adversaries in Decentralized Optimization for Non-Strongly Convex Objectives'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS
In: IFAC-PapersOnLine, Vol. 52, No. 20, 2019, p. 381-386.
Research output: Contribution to journal › Conference article › peer-review
}
TY - JOUR
T1 - Detection and Isolation of Adversaries in Decentralized Optimization for Non-Strongly Convex Objectives
AU - Ravi, Nikhil
AU - Scaglione, Anna
N1 - Funding Information: Non-Strongly C∗ onvex Obje∗ctives Nikhil Ravi∗ Anna Scaglione∗ Nikhil Ravi∗ Anna Scaglione∗ Nikhil Ravi∗ Anna Scaglione∗ ∗∗ School of ElNeikhictrilcaRl,aCvomi puAnternaandScaglionEnergyeEngineering, ∗School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, AZ 85281 USA School of Electrical, Computer and Energy Engineering, School of Electrical, Computer and Energy Engineering, (e-mail: {Nikhil.Ravi,Anna.Scaaggllione}@asu.edu). (e-mail: {Nikhil.Ravi,Anna.Scaglione}@asu.edu). (e-mail: {Nikhil.Ravi,Anna.Scaglione}@asu.edu). Abstract: Decentralized optimization has found a siflnificant utility in recent years, as a Abstract: Decentralized optimization has found a siflnificant utility in recent years, as a pinrfboemsrteirnsaicnecftla:ntdeDcdheecnceiiqnsutiroeanltipzoreodobvloeerpmctoisminiezbatithfiloednactuhara.ssWe fohofuilnedditmhaesnessiaifollnfnlioafirlciittayhnmtwsuhateirnleitrdyeesaiinliennrfeltctweonittnhoydleaearrafslne,d-saclsianlkae promisinfl technique to overcome the curse of dimensionality when dealinfl with larfle-scale inrfoemreinsicneflantdecdhenciiqsuioentporoobvleermcosminebtihfledactuar.sWe ohfileditmhesnesaiolfnloarliittyhmwshaerne rdeesailliiennflt twoitnhodlaeraflned-sclianlke failures, they however, are not inherently Byzanttiinnee fault-tolerant towards insider data injection faatitlaucrkess., tThheyishpoawpeevrerp,raorpeonseost ianhdeerceenttlryaBlizyezdanrtoibnuesftauslutb-tfolrlaedraienntttopwuashrd(sRinSsGidPe)r daalftloariinthjemctifoonr detection and isolation of malicious nodes in the network for optimization non-stronflly convex objectives. In the attack considered in this work, the malicious nodes follow the alflorithmic objectives. In the attack considered in this work, the malicious nodes follow the alflorithmic opbrojetoctciovless,.but can alter their local functions arbitrarily. However, we show that in sufficiently protocols, but can alter their local functions arbitrarily. However, we show that in sufficienttllyy structured problems, the method proposed is effective in revealinfl their presence. The alflorithm sistorluactteusreddetpercotbedlemnos,dtehsefrmoemthtohdeprreoflpuolaserdniosdeeffse,ctthiveereibnyremveitailfilnaftlinthfleitrhperielsl-eenffcec.tTs hoef amlfalolircitiohums isolates detected nodes from the reflular nodes, thereby mitiflatinfl the ill-effects of malicious isodlaetse.sWdetaelcstoedprnoovdidees pfreormformthaenrceeflmuleaarsunroedsesfo, rththereepbryopmoisteifdlamtineftlhtohde. ill-effects of malicious © 2019, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved. Keywords: decentralized optimization, multi-aflent systems, byzantine fault-tolerance, Keyworddss: decentralized optimization, multi-aflent systems, byzantine fault-tolerance, adevyewrosardrisa:ldoepcteinmtirzaalitzioedn,ofplrtaidmieiznatt-iboans,emd umlteit-raifclent systems, byzantine fault-tolerance, adKadevvyeeewrrrosarsardriisala:ldopoepctteiinmimtirzatzaalitziionoedn,,oflrfplrtadaidmiieeiznnattt-b-iboasedans,emdumetmlteit-rraiifcclent systems, byzantine fault-tolerance, adversarial optimization, flradient-based metric adversarial optimization, flradient-based metric 1. INTRODUCTION 1. INTRODUCTION 1. INTRODUCTION Anumberofmach1.ineINleTarninflRODUCTIOandbiflNdataproblemscan A number of machhiinnee learninfl and bifl data problems can Abenfulemnebrearliozefdmtaochtiankeeltehaernfionllflowanindflbfioflrmda:ta problems can be fleneralized to take the followinfl form: AbenfulemnebrearliozefdmtaochtiankeeltehaernfionllflowanindflNbfioflrmda:ta problems can be fleneralized to take the follow1infl∑Nform: be fleneralizedmitontaχk(ex)th=e fomlinlow1inf∑lNNformfi(:x)τ (1) x∈R x∈R N1 ∑N i xmmi∈iRnnd χχ ((xx)) == xmm∈iiRnnd N1 ∑i=1 ffi((xx))ττ ((1)1) x∈Rd x∈Rd N i=1 xm∈diRn χ (x) = xm∈iRn N i=1 fi(x)τ (1) where χ(·) : Rdd→ R is thedfllobia=l1objective which the where χ(·) :xR∈dR→Risthex∈RflloNbai=1lobjectivewhichthe nwohdeerse aχr(e·)tr:yRindfl →to Rcolilsectthiveelfyllombailniombijzeec.tiHveowehviecrh, the nowhdeerseaχre(·)tr:yRindfl→toRcolleiscthetivelyfllombainiml obizjeec.tiHveowwehviecr,h thethe where aχr(e·)tr:yRinfl →to Rcolilsectthiveelfyllombailniombijzeec.tiHveowehviecrh, the nodes aredtryinfl to collectively minimize. However, the nodes oanrley thrayvinefal ctcoescsotloletchtievierloywmnipnriimvaiztee.cHosotwfuevnecrt,iotnhse, fi(·) : Rd → R. There is a larfle class of decentralized nio(d·)es:oRnldy h→aveRa. cTcehsesretoitshaeirlaorwflne pclraivsaste cost functions, peer-to-pdeer alflorithms for solvinfl such decomposable op-tpiemeriz-taot-iopneeprraolbflloermitshmvisa fpoeresro-tlvoi-npfelesrucohndseecnosmuspopsraobtloecoolps-, timization problems via peer-to-peer consensus protocols, see Tsitsiklis et al. (1986); Nedićand Ozdafllar (2009) for see Tsitsiklis et al. (1986); Nedićand Ozdafllar (2009) for early contributions and see Boyd et al. (2011); Nedićet al. early contributions and see Boyd et al. (2011); Nedićet al. (2ear0l1y8)cofontrreibxteutnsionivseanlitedraseetureBoysudretvealys..(2011); Nedi´c et al. (2018) for extensive literature surveys. e2a0rl1y8)cofnotrreibxutetniosnivsealnitdersaeetuBreoysdurevteayls..(2011); Nedićet al. While these alflorithms are resilient to node or edfle fail-While these alflorithms are resilient to node or edfle fail-While these alflorithms are resilient to node or edfle failures, they are not however inherently resilient to insider-ures, they are not however inherently resilient to insider-based data injection attacks (see e.fl. Gentz et al. (2015); Blanchard et al. (2017); Gentz et al. (2016); Wu et al. Blanchard et al. (2017); Gentz et al. (2016); Wu et al. s2pl0ua1nr8rce)hd;arsSdiuflnnetdifaiacrala.nmt(2i0na1nt7ed)r;esGt heoannrtezrsoiefbaturdastl. (d(2e20c01e18n6)t))r;.alWiTzeuhdiseotphatails-. spurred siflnificant interest on robust decentralized opti-spurred siflnificant interest on robust decentralized optimization alflorithms. In literature, broadly speakinfl, there mization alflorithms. In literature, broadly speakinfl, there are two schools of solutions. In the first set of works, arethtowrso psrcohpoooslse omfetsholoudtsiotnos.reInflultahreizefirtshte objective by relaxinfl the hard consensus constraints, typically by usinfl aeultahxoinrsfl tphreophoasred mcoentsheondssustocornesftluralainrtizse, ttyhpeicaolblyjebctyivuesibnyfl ★ This research was supported in part by Cybersecurity for Energy ★relTahxiisnrfelsteharechhawrads csuopnpsoerntsedusincopnarsttrbayinCtysb,etrysepciucraitllyyfobryEunseirngfyl D★ eTlihveisryreSsyeastrecmh swparsosgurpampo,rotefdthienUp.aSr.tDbeypCarytbmeernsetcoufriEtynefrogryE, unnerdgeyr D★elivery Systems program, of the U.S. Department of Energy, under DoenTltihvraeisrcytreSDsyeOastrEecm0h0sw00pa7rso8sg0urpaampnod,rottefhdtehieNnUapt.aiSor.ntDableypSCacriyetbnmecerensetFcoouufrniEtdynaeftroigorynE, uCnneCrdgFeyr-contract DOE0000780 and the National Science Foundation CCF-BoSenlFtivrae1rc7yt14SD6yO7stEem0g0rs0a0pn7tr.o8g0Araanmnyd,ootpfhintehioeNnUast,.iSoa.nnDadlepfSiancridetinmncgeesntFeooxufpnErednsaesterigdoyn,inuCnCtdhFeisr-BSF 1714672 grant. Any opinions, and findings expressed in this BoSanFtterra1ica7tl14aD6rOe72tEh0go0rs0ae0no7tf.8t0AheannyaduottphhionerisoNnaasnt,dioadnnoadlnfSointcidneinenccgeessFeaoxruiplnyredrsaestefildoenctinCthCtohFsies-material are those of the authors and do not necessarily reflect those mfSatFtheer1ias7pl1o4an6res7o2trhsgo.rsaenotf. tAhenyauotphionrisonasn,dadnodnfoint dniencgesseaxriplyrersesefldectinthtohsies of the sponsors. ofattheeriaspl oanresotrhso.se of the authors and do not necessarily reflect those 2405-8963 © 2019, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved. Peer review under responsibility of International Federation of Automatic Control. Copyright © 2019 IFAC 381 10.1016/j.ifacol.2019.12.185 Copyright © 2019 IFAC 381 Publisher Copyright: © 2019 IFAC-PapersOnLine. All rights reseved.
PY - 2019
Y1 - 2019
N2 - Decentralized optimization has found a significant utility in recent years, as a promising technique to overcome the curse of dimensionality when dealing with large-scale inference and decision problems in big data. While these algorithms are resilient to node and link failures, they however, are not inherently Byzantine fault-tolerant towards insider data injection attacks. This paper proposes a decentralized robust subgradient push (RSGP) algorithm for detection and isolation of malicious nodes in the network for optimization non-strongly convex objectives. In the attack considered in this work, the malicious nodes follow the algorithmic protocols, but can alter their local functions arbitrarily. However, we show that in sufficiently structured problems, the method proposed is effective in revealing their presence. The algorithm isolates detected nodes from the regular nodes, thereby mitigating the ill-effects of malicious nodes. We also provide performance measures for the proposed method.
AB - Decentralized optimization has found a significant utility in recent years, as a promising technique to overcome the curse of dimensionality when dealing with large-scale inference and decision problems in big data. While these algorithms are resilient to node and link failures, they however, are not inherently Byzantine fault-tolerant towards insider data injection attacks. This paper proposes a decentralized robust subgradient push (RSGP) algorithm for detection and isolation of malicious nodes in the network for optimization non-strongly convex objectives. In the attack considered in this work, the malicious nodes follow the algorithmic protocols, but can alter their local functions arbitrarily. However, we show that in sufficiently structured problems, the method proposed is effective in revealing their presence. The algorithm isolates detected nodes from the regular nodes, thereby mitigating the ill-effects of malicious nodes. We also provide performance measures for the proposed method.
KW - adversarial optimization
KW - byzantine fault-tolerance
KW - decentralized optimization
KW - gradient-based metric
KW - multi-agent systems
UR - http://www.scopus.com/inward/record.url?scp=85082692892&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85082692892&partnerID=8YFLogxK
U2 - 10.1016/j.ifacol.2019.12.185
DO - 10.1016/j.ifacol.2019.12.185
M3 - Conference article
AN - SCOPUS:85082692892
SN - 2405-8963
VL - 52
SP - 381
EP - 386
JO - IFAC-PapersOnLine
JF - IFAC-PapersOnLine
IS - 20
T2 - 8th IFAC Workshop on Distributed Estimation and Control in Networked Systems, NECSYS 2019
Y2 - 16 September 2019 through 17 September 2019
ER -